** 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: where.c,v 1.164 2005/08/19 19:14:13 drh Exp $
*/
#include "sqliteInt.h"

/*
** The number of bits in a Bitmask.  "BMS" means "BitMask Size".
*/
#define BMS  (sizeof(Bitmask)*8)
................................................................................
** 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 */
  u16 idx;                /* Index of this term in pWC->a[] */
  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 operator;           /* 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 */
................................................................................
    sqliteFree(pWC->a);
  }
}

/*
** Add a new entries to the WhereClause structure.  Increase the allocated
** space as necessary.





*/
static WhereTerm *whereClauseInsert(WhereClause *pWC, Expr *p, int flags){
  WhereTerm *pTerm;

  if( pWC->nTerm>=pWC->nSlot ){
    WhereTerm *pOld = pWC->a;
    pWC->a = sqliteMalloc( sizeof(pWC->a[0])*pWC->nSlot*2 );
    if( pWC->a==0 ) return 0;
    memcpy(pWC->a, pOld, sizeof(pWC->a[0])*pWC->nTerm);
    if( pOld!=pWC->aStatic ){
      sqliteFree(pOld);
    }
    pWC->nSlot *= 2;
  }
  pTerm = &pWC->a[pWC->nTerm];
  pTerm->idx = pWC->nTerm;
  pWC->nTerm++;
  pTerm->pExpr = p;
  pTerm->flags = flags;
  pTerm->pWC = pWC;
  pTerm->iParent = -1;
  return pTerm;
}

/*
** This routine identifies subexpressions in the WHERE clause where
** each subexpression is separate by the AND operator or some other
** operator specified in the op parameter.  The WhereClause structure
** is filled with pointers to subexpressions.  For example:
................................................................................
      return pTerm;
    }
  }
  return 0;
}

/* Forward reference */
static void exprAnalyze(SrcList*, ExprMaskSet*, WhereTerm*);

/*
** Call exprAnalyze on all terms in a WHERE clause.  
**
**
*/
static void exprAnalyzeAll(
  SrcList *pTabList,       /* the FROM clause */
  ExprMaskSet *pMaskSet,   /* table masks */
  WhereClause *pWC         /* the WHERE clause to be analyzed */
){
  WhereTerm *pTerm;
  int i;
  for(i=pWC->nTerm-1, pTerm=pWC->a; i>=0; i--, pTerm++){
    exprAnalyze(pTabList, pMaskSet, pTerm);
  }
}

#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
................................................................................
** 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.  
*/
static void exprAnalyze(
  SrcList *pSrc,            /* the FROM clause */
  ExprMaskSet *pMaskSet,    /* table masks */
  WhereTerm *pTerm          /* the WHERE clause term to be analyzed */

){

  Expr *pExpr = pTerm->pExpr;
  Bitmask prereqLeft;
  Bitmask prereqAll;
  int idxRight;
  int nPattern;
  int isComplete;

................................................................................
      pTerm->leftColumn = pLeft->iColumn;
      pTerm->operator = operatorMask(pExpr->op);
    }
    if( pRight && pRight->op==TK_COLUMN ){
      WhereTerm *pNew;
      Expr *pDup;
      if( pTerm->leftCursor>=0 ){

        pDup = sqlite3ExprDup(pExpr);
        pNew = whereClauseInsert(pTerm->pWC, pDup, TERM_VIRTUAL|TERM_DYNAMIC);
        if( pNew==0 ) return;

        pNew->iParent = pTerm->idx;

        pTerm->nChild = 1;
        pTerm->flags |= TERM_COPIED;
      }else{
        pDup = pExpr;
        pNew = pTerm;
      }
      exprCommute(pDup);
................................................................................
    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;
      WhereTerm *pNewTerm;
      pNewExpr = sqlite3Expr(ops[i], sqlite3ExprDup(pExpr->pLeft),
                             sqlite3ExprDup(pList->a[i].pExpr), 0);
      pNewTerm = whereClauseInsert(pTerm->pWC, pNewExpr,
                                   TERM_VIRTUAL|TERM_DYNAMIC);
      exprAnalyze(pSrc, pMaskSet, pNewTerm);

      pNewTerm->iParent = pTerm->idx;
    }
    pTerm->nChild = 2;
  }
#endif /* SQLITE_OMIT_BETWEEN_OPTIMIZATION */

#ifndef SQLITE_OMIT_OR_OPTIMIZATION
  /* Attempt to convert OR-connected terms into an IN operator so that
................................................................................
    int ok;
    int i, j;
    int iColumn, iCursor;
    WhereClause sOr;
    WhereTerm *pOrTerm;

    assert( (pTerm->flags & TERM_DYNAMIC)==0 );
    whereClauseInit(&sOr, pTerm->pWC->pParse);
    whereSplit(&sOr, pExpr, TK_OR);
    exprAnalyzeAll(pSrc, pMaskSet, &sOr);
    assert( sOr.nTerm>0 );
    j = 0;
    do{
      iColumn = sOr.a[j].leftColumn;
      iCursor = sOr.a[j].leftCursor;
................................................................................
        pDup->iTable = iCursor;
        pDup->iColumn = iColumn;
      }
      pNew = sqlite3Expr(TK_IN, pDup, 0, 0);
      if( pNew ) pNew->pList = pList;
      pTerm->pExpr = pNew;
      pTerm->flags |= TERM_DYNAMIC;
      exprAnalyze(pSrc, pMaskSet, pTerm);

    }
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(pTerm->pWC->pParse->db, pExpr, &nPattern, &isComplete) ){
    Expr *pLeft, *pRight;
    Expr *pStr1, *pStr2;
    Expr *pNewExpr1, *pNewExpr2;
    WhereTerm *pNewTerm1, *pNewTerm2;

    pLeft = pExpr->pList->a[1].pExpr;
    pRight = pExpr->pList->a[0].pExpr;
    pStr1 = sqlite3Expr(TK_STRING, 0, 0, 0);
    if( pStr1 ){
      sqlite3TokenCopy(&pStr1->token, &pRight->token);
      pStr1->token.n = nPattern;
    }
    pStr2 = sqlite3ExprDup(pStr1);
    if( pStr2 ){
      assert( pStr2->token.dyn );
      ++*(u8*)&pStr2->token.z[nPattern-1];
    }
    pNewExpr1 = sqlite3Expr(TK_GE, sqlite3ExprDup(pLeft), pStr1, 0);
    pNewTerm1 = whereClauseInsert(pTerm->pWC, pNewExpr1,
                                  TERM_VIRTUAL|TERM_DYNAMIC);
    exprAnalyze(pSrc, pMaskSet, pNewTerm1);
    pNewExpr2 = sqlite3Expr(TK_LT, sqlite3ExprDup(pLeft), pStr2, 0);
    pNewTerm2 = whereClauseInsert(pTerm->pWC, pNewExpr2,
                                 TERM_VIRTUAL|TERM_DYNAMIC);
    exprAnalyze(pSrc, pMaskSet, pNewTerm2);

    if( isComplete ){

      pNewTerm2->iParent = pTerm->idx;
      pNewTerm1->iParent = pTerm->idx;
      pTerm->nChild = 2;
    }
  }
#endif /* SQLITE_OMIT_LIKE_OPTIMIZATION */
}

** 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: where.c,v 1.165 2005/08/24 03:52:19 drh Exp $
*/
#include "sqliteInt.h"

/*
** The number of bits in a Bitmask.  "BMS" means "BitMask Size".
*/
#define BMS  (sizeof(Bitmask)*8)
................................................................................
** 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 operator;           /* 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 */
................................................................................
    sqliteFree(pWC->a);
  }
}

/*
** Add a new entries to the WhereClause structure.  Increase the allocated
** space as necessary.
**
** 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 ) 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 separate by the AND operator or some other
** operator specified in the op parameter.  The WhereClause structure
** is filled with pointers to subexpressions.  For example:
................................................................................
      return pTerm;
    }
  }
  return 0;
}

/* Forward reference */
static void exprAnalyze(SrcList*, ExprMaskSet*, WhereClause*, int);

/*
** Call exprAnalyze on all terms in a WHERE clause.  
**
**
*/
static void exprAnalyzeAll(
  SrcList *pTabList,       /* the FROM clause */
  ExprMaskSet *pMaskSet,   /* table masks */
  WhereClause *pWC         /* the WHERE clause to be analyzed */
){

  int i;
  for(i=pWC->nTerm-1; i>=0; i--){
    exprAnalyze(pTabList, pMaskSet, 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
................................................................................
** 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.  
*/
static void exprAnalyze(
  SrcList *pSrc,            /* the FROM clause */
  ExprMaskSet *pMaskSet,    /* table masks */
  WhereClause *pWC,         /* the WHERE clause */
  int idxTerm               /* Index of the term to be analyzed */
){
  WhereTerm *pTerm = &pWC->a[idxTerm];
  Expr *pExpr = pTerm->pExpr;
  Bitmask prereqLeft;
  Bitmask prereqAll;
  int idxRight;
  int nPattern;
  int isComplete;

................................................................................
      pTerm->leftColumn = pLeft->iColumn;
      pTerm->operator = operatorMask(pExpr->op);
    }
    if( pRight && pRight->op==TK_COLUMN ){
      WhereTerm *pNew;
      Expr *pDup;
      if( pTerm->leftCursor>=0 ){
        int idxNew;
        pDup = sqlite3ExprDup(pExpr);
        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);
................................................................................
    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(ops[i], sqlite3ExprDup(pExpr->pLeft),
                             sqlite3ExprDup(pList->a[i].pExpr), 0);

      idxNew = whereClauseInsert(pWC, pNewExpr, TERM_VIRTUAL|TERM_DYNAMIC);
      exprAnalyze(pSrc, pMaskSet, pWC, idxNew);
      pTerm = &pWC->a[idxTerm];
      pWC->a[idxNew].iParent = idxTerm;
    }
    pTerm->nChild = 2;
  }
#endif /* SQLITE_OMIT_BETWEEN_OPTIMIZATION */

#ifndef SQLITE_OMIT_OR_OPTIMIZATION
  /* Attempt to convert OR-connected terms into an IN operator so that
................................................................................
    int ok;
    int i, j;
    int iColumn, iCursor;
    WhereClause sOr;
    WhereTerm *pOrTerm;

    assert( (pTerm->flags & TERM_DYNAMIC)==0 );
    whereClauseInit(&sOr, pWC->pParse);
    whereSplit(&sOr, pExpr, TK_OR);
    exprAnalyzeAll(pSrc, pMaskSet, &sOr);
    assert( sOr.nTerm>0 );
    j = 0;
    do{
      iColumn = sOr.a[j].leftColumn;
      iCursor = sOr.a[j].leftCursor;
................................................................................
        pDup->iTable = iCursor;
        pDup->iColumn = iColumn;
      }
      pNew = sqlite3Expr(TK_IN, pDup, 0, 0);
      if( pNew ) pNew->pList = pList;
      pTerm->pExpr = pNew;
      pTerm->flags |= TERM_DYNAMIC;
      exprAnalyze(pSrc, pMaskSet, pWC, idxTerm);
      pTerm = &pWC->a[idxTerm];
    }
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(pWC->pParse->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 = sqlite3Expr(TK_STRING, 0, 0, 0);
    if( pStr1 ){
      sqlite3TokenCopy(&pStr1->token, &pRight->token);
      pStr1->token.n = nPattern;
    }
    pStr2 = sqlite3ExprDup(pStr1);
    if( pStr2 ){
      assert( pStr2->token.dyn );
      ++*(u8*)&pStr2->token.z[nPattern-1];
    }
    pNewExpr1 = sqlite3Expr(TK_GE, sqlite3ExprDup(pLeft), pStr1, 0);

    idxNew1 = whereClauseInsert(pWC, pNewExpr1, TERM_VIRTUAL|TERM_DYNAMIC);
    exprAnalyze(pSrc, pMaskSet, pWC, idxNew1);
    pNewExpr2 = sqlite3Expr(TK_LT, sqlite3ExprDup(pLeft), pStr2, 0);

    idxNew2 = whereClauseInsert(pWC, pNewExpr2, TERM_VIRTUAL|TERM_DYNAMIC);
    exprAnalyze(pSrc, pMaskSet, 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 */
}

#    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 use of indices in WHERE clases.
#
# $Id: where.test,v 1.32 2005/07/28 16:51:51 drh Exp $

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

# Build some test data
#
do_test where-1.0 {
................................................................................
  count {SELECT (w) FROM t1 WHERE ((w)+(1))==(98)}
} {97 99}


# Do the same kind of thing except use a join as the data source.
#
do_test where-2.1 {

  count {
    SELECT w, p FROM t2, t1
    WHERE x=q AND y=s AND r=8977
  }
} {34 67 6}
do_test where-2.2 {
  count {
................................................................................
    set v [expr {!$v}]
    return $v
  }
  execsql {
    SELECT count(*) FROM t1 WHERE tclvar('v1');
  }
} {50}




































integrity_check {where-99.0}

finish_test

#    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 use of indices in WHERE clases.
#
# $Id: where.test,v 1.33 2005/08/24 03:52:19 drh Exp $

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

# Build some test data
#
do_test where-1.0 {
................................................................................
  count {SELECT (w) FROM t1 WHERE ((w)+(1))==(98)}
} {97 99}


# Do the same kind of thing except use a join as the data source.
#
do_test where-2.1 {
btree_breakpoint
  count {
    SELECT w, p FROM t2, t1
    WHERE x=q AND y=s AND r=8977
  }
} {34 67 6}
do_test where-2.2 {
  count {
................................................................................
    set v [expr {!$v}]
    return $v
  }
  execsql {
    SELECT count(*) FROM t1 WHERE tclvar('v1');
  }
} {50}

# Ticket #1376.  The query below was causing a segfault.
# The problem was the age-old error of calling realloc() on an
# array while there are still pointers to individual elements of
# that array.
#
do_test where-11.1 {
btree_breakpoint
  execsql {
   CREATE TABLE t99(Dte INT, X INT);
   DELETE FROM t99 WHERE (Dte = 2451337) OR (Dte = 2451339) OR
     (Dte BETWEEN 2451345 AND 2451347) OR (Dte = 2451351) OR 
     (Dte BETWEEN 2451355 AND 2451356) OR (Dte = 2451358) OR
     (Dte = 2451362) OR (Dte = 2451365) OR (Dte = 2451367) OR
     (Dte BETWEEN 2451372 AND 2451376) OR (Dte BETWEEN 2451382 AND 2451384) OR
     (Dte = 2451387) OR (Dte BETWEEN 2451389 AND 2451391) OR 
     (Dte BETWEEN 2451393 AND 2451395) OR (Dte = 2451400) OR 
     (Dte = 2451402) OR (Dte = 2451404) OR (Dte BETWEEN 2451416 AND 2451418) OR 
     (Dte = 2451422) OR (Dte = 2451426) OR (Dte BETWEEN 2451445 AND 2451446) OR
     (Dte = 2451456) OR (Dte = 2451458) OR (Dte BETWEEN 2451465 AND 2451467) OR
     (Dte BETWEEN 2451469 AND 2451471) OR (Dte = 2451474) OR
     (Dte BETWEEN 2451477 AND 2451501) OR (Dte BETWEEN 2451503 AND 2451509) OR
     (Dte BETWEEN 2451511 AND 2451514) OR (Dte BETWEEN 2451518 AND 2451521) OR
     (Dte BETWEEN 2451523 AND 2451531) OR (Dte BETWEEN 2451533 AND 2451537) OR
     (Dte BETWEEN 2451539 AND 2451544) OR (Dte BETWEEN 2451546 AND 2451551) OR
     (Dte BETWEEN 2451553 AND 2451555) OR (Dte = 2451557) OR
     (Dte BETWEEN 2451559 AND 2451561) OR (Dte = 2451563) OR
     (Dte BETWEEN 2451565 AND 2451566) OR (Dte BETWEEN 2451569 AND 2451571) OR 
     (Dte = 2451573) OR (Dte = 2451575) OR (Dte = 2451577) OR (Dte = 2451581) OR
     (Dte BETWEEN 2451583 AND 2451586) OR (Dte BETWEEN 2451588 AND 2451592) OR 
     (Dte BETWEEN 2451596 AND 2451598) OR (Dte = 2451600) OR
     (Dte BETWEEN 2451602 AND 2451603) OR (Dte = 2451606) OR (Dte = 2451611);
  }
} {}


integrity_check {where-99.0}

finish_test