** 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.172 2005/09/16 02:38:11 drh Exp $
*/
#include "sqliteInt.h"

/*
** The number of bits in a Bitmask.  "BMS" means "BitMask Size".
*/
#define BMS  (sizeof(Bitmask)*8)
................................................................................
** 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 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);
  if( p->pSelect ){
    Select *pS = p->pSelect;
    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;
}
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;













}

/*
** 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".
*/
................................................................................
  Bitmask prereqLeft;
  Bitmask prereqAll;
  int nPattern;
  int isComplete;

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





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

  pTerm->prereqAll = prereqAll = exprTableUsage(pMaskSet, pExpr);
  pTerm->leftCursor = -1;
  pTerm->iParent = -1;
  pTerm->operator = 0;
  if( allowedOp(pExpr->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->operator = operatorMask(pExpr->op);
    }
    if( pRight && pRight->op==TK_COLUMN ){
      WhereTerm *pNew;
................................................................................
    }
    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
  ** they can make use of indices.






  */
  else if( pExpr->op==TK_OR ){
    int ok;
    int i, j;
    int iColumn, iCursor;
    WhereClause sOr;
    WhereTerm *pOrTerm;

** 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.173 2005/09/17 13:07:13 drh Exp $
*/
#include "sqliteInt.h"

/*
** The number of bits in a Bitmask.  "BMS" means "BitMask Size".
*/
#define BMS  (sizeof(Bitmask)*8)
................................................................................
** 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".
*/
................................................................................
  Bitmask prereqLeft;
  Bitmask prereqAll;
  int nPattern;
  int isComplete;

  if( sqlite3_malloc_failed ) return;
  prereqLeft = exprTableUsage(pMaskSet, pExpr->pLeft);
  if( pExpr->op==TK_IN ){
    assert( pExpr->pRight==0 );
    pTerm->prereqRight = exprListTableUsage(pMaskSet, pExpr->pList)
                          | exprSelectTableUsage(pMaskSet, pExpr->pSelect);
  }else{
    pTerm->prereqRight = exprTableUsage(pMaskSet, pExpr->pRight);
  }
  pTerm->prereqAll = prereqAll = exprTableUsage(pMaskSet, pExpr);
  pTerm->leftCursor = -1;
  pTerm->iParent = -1;
  pTerm->operator = 0;
  if( allowedOp(pExpr->op) && (pTerm->prereqRight & prereqLeft)==0 ){
    Expr *pLeft = pExpr->pLeft;
    Expr *pRight = pExpr->pRight;
    assert( prereqAll == (pTerm->prereqRight | prereqLeft) ); /* ticket 1433 */
    if( pLeft->op==TK_COLUMN ){
      pTerm->leftCursor = pLeft->iTable;
      pTerm->leftColumn = pLeft->iColumn;
      pTerm->operator = operatorMask(pExpr->op);
    }
    if( pRight && pRight->op==TK_COLUMN ){
      WhereTerm *pNew;
................................................................................
    }
    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
  ** they can make use of indices.  Example:
  **
  **      x = expr1  OR  expr2 = x  OR  x = expr3
  **
  ** is converted into
  **
  **      x IN (expr1,expr2,expr3)
  */
  else if( pExpr->op==TK_OR ){
    int ok;
    int i, j;
    int iColumn, iCursor;
    WhereClause sOr;
    WhereTerm *pOrTerm;

# 2005 September 17
#
# 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.
#
# This file implements tests to verify that ticket #1433 has been
# fixed.  
#
# The problem in ticket #1433 was that the dependencies on the right-hand
# side of an IN operator were not being checked correctly.  So in an
# expression of the form:
#
#         t1.x IN (1,t2.b,3)
#
# the optimizer was missing the fact that the right-hand side of the IN
# depended on table t2.  It was checking dependencies based on the
# Expr.pRight field rather than Expr.pList and Expr.pSelect.  
#
# Such a bug could be verifed using a less elaborate test case.  But
# this test case (from the original bug poster) exercises so many different
# parts of the system all at once, that it seemed like a good one to
# include in the test suite. 
#
# $Id: tkt1443.test,v 1.1 2005/09/17 13:07:13 drh Exp $

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


# Construct the sample database.
#
do_test tkt1433-1.0 {
  sqlite3 db :memory:
  execsql {
    CREATE TABLE Items(
    	itemId integer primary key,
    	 item str unique
    );
    INSERT INTO "Items" VALUES(0, 'ALL');
    INSERT INTO "Items" VALUES(1, 'double:source');
    INSERT INTO "Items" VALUES(2, 'double');
    INSERT INTO "Items" VALUES(3, 'double:runtime');
    INSERT INTO "Items" VALUES(4, '.*:runtime');
    
    CREATE TABLE Labels(
    	labelId INTEGER PRIMARY KEY,
    	label STR UNIQUE
    );
    INSERT INTO "Labels" VALUES(0, 'ALL');
    INSERT INTO "Labels" VALUES(1, 'localhost@rpl:linux');
    INSERT INTO "Labels" VALUES(2, 'localhost@rpl:branch');
    
    CREATE TABLE LabelMap(
    	itemId INTEGER,
    	labelId INTEGER,
    	branchId integer
    );
    INSERT INTO "LabelMap" VALUES(1, 1, 1);
    INSERT INTO "LabelMap" VALUES(2, 1, 1);
    INSERT INTO "LabelMap" VALUES(3, 1, 1);
    INSERT INTO "LabelMap" VALUES(1, 2, 2);
    INSERT INTO "LabelMap" VALUES(2, 2, 3);
    INSERT INTO "LabelMap" VALUES(3, 2, 3);
    
    CREATE TABLE Users (
    	userId INTEGER PRIMARY KEY,
    	user STRING UNIQUE,
    	salt BINARY,
    	password STRING
    );
    INSERT INTO "Users" VALUES(1, 'test', 'Šæ$d',
               '43ba0f45014306bd6df529551ffdb3df');
    INSERT INTO "Users" VALUES(2, 'limited', 'ªš>S',
               'cf07c8348fdf675cc1f7696b7d45191b');
    CREATE TABLE UserGroups (
    	userGroupId INTEGER PRIMARY KEY,
    	userGroup STRING UNIQUE
    );
    INSERT INTO "UserGroups" VALUES(1, 'test');
    INSERT INTO "UserGroups" VALUES(2, 'limited');
    
    CREATE TABLE UserGroupMembers (
    	userGroupId INTEGER,
    	userId INTEGER
    );
    INSERT INTO "UserGroupMembers" VALUES(1, 1);
    INSERT INTO "UserGroupMembers" VALUES(2, 2);
    
    CREATE TABLE Permissions (
    	userGroupId INTEGER,
    	labelId INTEGER NOT NULL,
    	itemId INTEGER NOT NULL,
    	write INTEGER,
    	capped INTEGER,
    	admin INTEGER
    );
    INSERT INTO "Permissions" VALUES(1, 0, 0, 1, 0, 1);
    INSERT INTO "Permissions" VALUES(2, 2, 4, 0, 0, 0);
  }
} {}

# Run the query with an index
#
do_test tkt1443-1.1 {
  execsql {
    select distinct
        Items.Item as trove, UP.pattern as pattern
    from
       ( select
           Permissions.labelId as labelId,
           PerItems.item as pattern
         from
           Users, UserGroupMembers, Permissions
           left outer join Items as PerItems
                 on Permissions.itemId = PerItems.itemId
         where
               Users.user = 'limited'
           and Users.userId = UserGroupMembers.userId
           and UserGroupMembers.userGroupId = Permissions.userGroupId
       ) as UP join LabelMap on ( UP.labelId = 0 or
                                  UP.labelId = LabelMap.labelId ),
       Labels, Items
    where
        Labels.label = 'localhost@rpl:branch'
    and Labels.labelId = LabelMap.labelId
    and LabelMap.itemId = Items.itemId
    ORDER BY +trove, +pattern
  }
} {double .*:runtime double:runtime .*:runtime double:source .*:runtime}

# Create an index and rerun the query. 
# Verify that the results are the same
#
do_test tkt1443-1.2 {
  execsql {
    CREATE UNIQUE INDEX PermissionsIdx
         ON Permissions(userGroupId, labelId, itemId);
    select distinct
        Items.Item as trove, UP.pattern as pattern
    from
       ( select
           Permissions.labelId as labelId,
           PerItems.item as pattern
         from
           Users, UserGroupMembers, Permissions
           left outer join Items as PerItems
                 on Permissions.itemId = PerItems.itemId
         where
               Users.user = 'limited'
           and Users.userId = UserGroupMembers.userId
           and UserGroupMembers.userGroupId = Permissions.userGroupId
       ) as UP join LabelMap on ( UP.labelId = 0 or
                                  UP.labelId = LabelMap.labelId ),
       Labels, Items
    where
        Labels.label = 'localhost@rpl:branch'
    and Labels.labelId = LabelMap.labelId
    and LabelMap.itemId = Items.itemId
    ORDER BY +trove, +pattern
  }
} {double .*:runtime double:runtime .*:runtime double:source .*:runtime}

finish_test