**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** This header file defines the interface that the SQLite library
** presents to client programs.
**
** @(#) $Id: sqlite.h.in,v 1.169 2006/06/12 11:24:37 danielk1977 Exp $
*/
#ifndef _SQLITE3_H_
#define _SQLITE3_H_
#include <stdarg.h>     /* Needed for the definition of va_list */

/*
** Make sure we can call this stuff from C++.
................................................................................
  const char *zFile,    /* Name of the shared library containing extension */
  const char *zProc,    /* Entry point.  Derived from zFile if 0 */
  char **pzErrMsg       /* Put error message here if not 0 */
);

/*
****** EXPERIMENTAL - subject to change without notice **************











*/
typedef struct sqlite3_vtab sqlite3_vtab;
typedef struct sqlite3_index_info sqlite3_index_info;
typedef struct sqlite3_vtab_cursor sqlite3_vtab_cursor;
typedef struct sqlite3_module sqlite3_module;






struct sqlite3_module {
  int iVersion;
  const char *zName;
  void *pAux;
  int (*xCreate)(sqlite3*, const sqlite3_module *pModule,
               int argc, char **argv,
               sqlite3_vtab **ppVTab);
................................................................................
  int (*xDelete)(sqlite3_vtab *pVTab, sqlite_int64 rowid);
  int (*xBegin)(sqlite3_vtab *pVTab);
  int (*xSync)(sqlite3_vtab *pVTab);
  int (*xCommit)(sqlite3_vtab *pVTab);
  int (*xRollback)(sqlite3_vtab *pVTab);
  int (*xIsInTrans)(sqlite3_vtab *pVTab);
};














































struct sqlite3_index_info {
  /* Inputs */
  int nConstraint;
  struct sqlite3_index_constraint {
     int iColumn;

     unsigned char op;
     unsigned char omit;
  } *aConstraint;
  int nOrderBy;




  struct sqlite3_index_orderby {
     int iColumn;
     unsigned char desc;
  } *aOrderBy;


  /* Outputs */
  int idxNum;
  int columnCount;
  int *aColumn;





  int orderByConsumed;

};
#define SQLITE_INDEX_CONSTRAINT_EQ    1
#define SQLITE_INDEX_CONSTRAINT_GT    3
#define SQLITE_INDEX_CONSTRAINT_LE    4
#define SQLITE_INDEX_CONSTRAINT_LT    5
#define SQLITE_INDEX_CONSTRAINT_GE    6
#define SQLITE_INDEX_CONSTRAINT_MATCH 7







int sqlite3_create_module(
  sqlite3 *db, 

  const char *zName,
  const sqlite3_module *
);
































int sqlite3_declare_vtab(sqlite3*, const char *zCreateTable);













/*
** Undo the hack that converts floating point types to integer for
** builds on processors without floating point support.
*/
#ifdef SQLITE_OMIT_FLOATING_POINT
# undef double
#endif

#ifdef __cplusplus
}  /* End of the 'extern "C"' block */
#endif
#endif

**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** This header file defines the interface that the SQLite library
** presents to client programs.
**
** @(#) $Id: sqlite.h.in,v 1.170 2006/06/12 21:59:14 drh Exp $
*/
#ifndef _SQLITE3_H_
#define _SQLITE3_H_
#include <stdarg.h>     /* Needed for the definition of va_list */

/*
** Make sure we can call this stuff from C++.
................................................................................
  const char *zFile,    /* Name of the shared library containing extension */
  const char *zProc,    /* Entry point.  Derived from zFile if 0 */
  char **pzErrMsg       /* Put error message here if not 0 */
);

/*
****** EXPERIMENTAL - subject to change without notice **************
**
** The interface to the virtual-table mechanism is currently considered
** to be experimental.  The interface might change in incompatible ways.
** If this is a problem for you, do not use the interface at this time.
**
** When the virtual-table mechanism stablizes, we will declare the
** interface fixed, support it indefinitely, and remove this comment.
*/

/*
** Structures used by the virtual table interface
*/
typedef struct sqlite3_vtab sqlite3_vtab;
typedef struct sqlite3_index_info sqlite3_index_info;
typedef struct sqlite3_vtab_cursor sqlite3_vtab_cursor;
typedef struct sqlite3_module sqlite3_module;

/*
** A module is a class of virtual tables.  Each module is defined
** by an instance of the following structure.  This structure consists
** mostly of methods for the module.
*/
struct sqlite3_module {
  int iVersion;
  const char *zName;
  void *pAux;
  int (*xCreate)(sqlite3*, const sqlite3_module *pModule,
               int argc, char **argv,
               sqlite3_vtab **ppVTab);
................................................................................
  int (*xDelete)(sqlite3_vtab *pVTab, sqlite_int64 rowid);
  int (*xBegin)(sqlite3_vtab *pVTab);
  int (*xSync)(sqlite3_vtab *pVTab);
  int (*xCommit)(sqlite3_vtab *pVTab);
  int (*xRollback)(sqlite3_vtab *pVTab);
  int (*xIsInTrans)(sqlite3_vtab *pVTab);
};

/*
** The sqlite3_index_info structure and its substructures is used to
** pass information into and receive the reply from the xBestIndex
** method of an sqlite3_module.  The fields under **Inputs** are the
** inputs to xBestIndex and are read-only.  xBestIndex inserts its
** results into the **Outputs** fields.
**
** The aConstraint[] array records WHERE clause constraints of the
** form:
**
**         column OP expr
**
** Where OP is =, <, <=, >, or >=.  The particular operator is stored
** in aConstraint[].op.  The index of the column is stored in 
** aConstraint[].iColumn.  aConstraint[].usable is TRUE if the
** expr on the right-hand side can be evaluated (and thus the constraint
** is usable) and false if it cannot.
**
** The optimizer automatically inverts terms of the form "expr OP column"
** and makes other simplificatinos to the WHERE clause in an attempt to
** get as many WHERE clause terms into the form shown above as possible.
** The aConstraint[] array only reports WHERE clause terms in the correct
** form that refer to the particular virtual table being queried.
**
** Information about the ORDER BY clause is stored in aOrderBy[].
** Each term of aOrderBy records a column of the ORDER BY clause.
**
** The xBestIndex method must fill aConstraintUsage[] with information
** about what parameters to pass to xBestIndex.  If argvIndex>0 then
** the right-hand side of the corresponding aConstraint[] is evaluated
** and becomes the argvIndex-th entry in argv.  If aConstraintUsage[].omit
** is true, then the constraint is assumed to be fully handled by the
** virtual table and is not checked again by SQLite.
**
** The idxNum value is recorded and passed into xFilter.  
**
** The orderByConsumed means that output from xFilter will occur in
** the correct order to satisfy the ORDER BY clause so that no separate
** sorting step is required.
**
** The estimatedCost value is an estimate of the cost of doing the
** particular lookup.  A full scan of a table with N entries should have
** a cost of N.  A binary search of a table of N entries should have a
** cost of approximately log(N).
*/
struct sqlite3_index_info {
  /* Inputs */
  const int nConstraint;     /* Number of entries in aConstraint */
  const struct sqlite3_index_constraint {

     int iColumn;              /* Column on left-hand side of constraint */
     unsigned char op;         /* Constraint operator */



     unsigned char usable;     /* True if this constraint is usable */
     int iTermOffset;          /* Used internally - xBestIndex should ignore */
  } *const aConstraint;      /* Table of WHERE clause constraints */
  const int nOrderBy;        /* Number of terms in the ORDER BY clause */
  const struct sqlite3_index_orderby {
     int iColumn;              /* Column number */
     unsigned char desc;       /* True for DESC.  False for ASC. */

  } *const aOrderBy;         /* The ORDER BY clause */

  /* Outputs */



  struct sqlite3_index_constraint_usage {
    int argvIndex;           /* if >0, constraint is part of argv to xFilter */
    unsigned char omit;      /* Do not code a test for this constraint */
  } *const aConstraintUsage;
  int idxNum;                /* Index number passed to xFilter */
  int orderByConsumed;       /* True if output is already ordered */
  double estimatedCost;      /* Estimated cost of using this index */
};
#define SQLITE_INDEX_CONSTRAINT_EQ    2
#define SQLITE_INDEX_CONSTRAINT_GT    4
#define SQLITE_INDEX_CONSTRAINT_LE    8
#define SQLITE_INDEX_CONSTRAINT_LT    16
#define SQLITE_INDEX_CONSTRAINT_GE    32
#define SQLITE_INDEX_CONSTRAINT_MATCH 64

/*
** This routine is used to register a new module name with an SQLite
** connection.  Module names must be registered before creating new
** virtual tables on the module, or before using preexisting virtual
** tables of the module.
*/
int sqlite3_create_module(

  sqlite3 *db,               /* SQLite connection to register module with */
  const char *zName,         /* Name of the module */
  const sqlite3_module *     /* Methods for the module */
);

/*
** Every module implementation uses a subclass of the following structure
** to describe a particular instance of the module.  Each subclass will
** be taylored to the specific needs of the module implementation.   The
** purpose of this superclass is to define certain fields that are common
** to all module implementations.
*/
struct sqlite3_vtab {
  sqlite3_module *pModule;  /* The module for this virtual table */
  /* Virtual table implementations will typically add additional fields */
};

/* Every module implementation uses a subclass of the following structure
** to describe cursors that point into the virtual table and are used
** to loop through the virtual table.  Cursors are created using the
** xOpen method of the module.  Each module implementation will define
** the content of a cursor structure to suit its own needs.
**
** This superclass exists in order to define fields of the cursor that
** are common to all implementations.
*/
struct sqlite3_vtab_cursor {
  sqlite3_vtab *pVtab;      /* Virtual table of this cursor */
  /* Virtual table implementations will typically add additional fields */
};

/*
** The xCreate and xConnect methods of a module use the following API
** to declare the format (the names and datatypes of the columns) of
** the virtual tables they implement.
*/
int sqlite3_declare_vtab(sqlite3*, const char *zCreateTable);

/*
** The interface to the virtual-table mechanism defined above (back up
** to a comment remarkably similar to this one) is currently considered
** to be experimental.  The interface might change in incompatible ways.
** If this is a problem for you, do not use the interface at this time.
**
** When the virtual-table mechanism stablizes, we will declare the
** interface fixed, support it indefinitely, and remove this comment.
**
****** EXPERIMENTAL - subject to change without notice **************
*/

/*
** Undo the hack that converts floating point types to integer for
** builds on processors without floating point support.
*/
#ifdef SQLITE_OMIT_FLOATING_POINT
# undef double
#endif

#ifdef __cplusplus
}  /* End of the 'extern "C"' block */
#endif
#endif

**    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.
**
*************************************************************************
** Internal interface definitions for SQLite.
**
** @(#) $Id: sqliteInt.h,v 1.501 2006/06/12 16:01:22 danielk1977 Exp $
*/
#ifndef _SQLITEINT_H_
#define _SQLITEINT_H_

/*
** Extra interface definitions for those who need them
*/
................................................................................
  int brk;              /* Jump here to break out of the loop */
  int cont;             /* Jump here to continue with the next loop cycle */
  int top;              /* First instruction of interior of the loop */
  int op, p1, p2;       /* Opcode used to terminate the loop */
  int nEq;              /* Number of == or IN constraints on this loop */
  int nIn;              /* Number of IN operators constraining this loop */
  int *aInLoop;         /* Loop terminators for IN operators */

};

/*
** The WHERE clause processing routine has two halves.  The
** first part does the start of the WHERE loop and the second
** half does the tail of the WHERE loop.  An instance of
** this structure is returned by the first half and passed

**    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.
**
*************************************************************************
** Internal interface definitions for SQLite.
**
** @(#) $Id: sqliteInt.h,v 1.502 2006/06/12 21:59:14 drh Exp $
*/
#ifndef _SQLITEINT_H_
#define _SQLITEINT_H_

/*
** Extra interface definitions for those who need them
*/
................................................................................
  int brk;              /* Jump here to break out of the loop */
  int cont;             /* Jump here to continue with the next loop cycle */
  int top;              /* First instruction of interior of the loop */
  int op, p1, p2;       /* Opcode used to terminate the loop */
  int nEq;              /* Number of == or IN constraints on this loop */
  int nIn;              /* Number of IN operators constraining this loop */
  int *aInLoop;         /* Loop terminators for IN operators */
  sqlite3_index_info *pIdxInfo;  /* Index information for virtual tables */
};

/*
** The WHERE clause processing routine has two halves.  The
** first part does the start of the WHERE loop and the second
** half does the tail of the WHERE loop.  An instance of
** this structure is returned by the first half and passed

**
** Various scripts scan this source file in order to generate HTML
** documentation, headers files, or other derived files.  The formatting
** of the code in this file is, therefore, important.  See other comments
** in this file for details.  If in doubt, do not deviate from existing
** commenting and indentation practices when changing or adding code.
**
** $Id: vdbe.c,v 1.553 2006/06/12 16:01:22 danielk1977 Exp $
*/
#include "sqliteInt.h"
#include "os.h"
#include <ctype.h>
#include "vdbeInt.h"

/*
................................................................................
**
** P3 is the name of a virtual table in database P1.  Call the xDestroy method
** of that table.
*/
case OP_VDestroy: {
  rc = sqlite3VtabCallDestroy(db, pOp->p1, pOp->p3);
  break;



































































}
#endif /* SQLITE_OMIT_VIRTUALTABLE */

/* An other opcode is illegal...
*/
default: {
  assert( 0 );

**
** Various scripts scan this source file in order to generate HTML
** documentation, headers files, or other derived files.  The formatting
** of the code in this file is, therefore, important.  See other comments
** in this file for details.  If in doubt, do not deviate from existing
** commenting and indentation practices when changing or adding code.
**
** $Id: vdbe.c,v 1.554 2006/06/12 21:59:14 drh Exp $
*/
#include "sqliteInt.h"
#include "os.h"
#include <ctype.h>
#include "vdbeInt.h"

/*
................................................................................
**
** P3 is the name of a virtual table in database P1.  Call the xDestroy method
** of that table.
*/
case OP_VDestroy: {
  rc = sqlite3VtabCallDestroy(db, pOp->p1, pOp->p3);
  break;
}
#endif /* SQLITE_OMIT_VIRTUALTABLE */

#ifndef SQLITE_OMIT_VIRTUALTABLE
/* Opcode: VOpen P1 * P3
**
** P3 is a pointer to a virtual table object, an sqlite3_vtab structure.
** P1 is a cursor number.  This opcode opens a cursor to the virtual
** table and stores that cursor in P1.
*/
case OP_VOpen: {
  break;
}
#endif /* SQLITE_OMIT_VIRTUALTABLE */

#ifndef SQLITE_OMIT_VIRTUALTABLE
/* Opcode: VFilter P1 P2 *
**
** P1 is a cursor opened using VOpen.  P2 is an address to jump to if
** the filtered result set is empty.
**
** This opcode invokes the xFilter method on the virtual table specified
** by P1.  The index number parameter to xFilter is the top of the stack.
** Next down on the stack is the argc parameter.  Beneath the
** next of stack are argc additional parameters which are passed to
** xFilter as argv.  The index number, argc, and all argv stack values
** are popped from the stack before this instruction completes.
**
** A jump is made to P2 if the result set after filtering would be 
** empty.
*/
case OP_VFilter: {
  break;
}
#endif /* SQLITE_OMIT_VIRTUALTABLE */

#ifndef SQLITE_OMIT_VIRTUALTABLE
/* Opcode: VRowid P1 * *
**
** Push an integer onto the stack which is the rowid of
** the virtual-table that the P1 cursor is pointing to.
*/
case OP_VRowid: {
  break;
}
#endif /* SQLITE_OMIT_VIRTUALTABLE */

#ifndef SQLITE_OMIT_VIRTUALTABLE
/* Opcode: VColumn P1 P2 *
**
** Push onto the stack the value of the P2-th column of
** the row of the virtual-table that the P1 cursor is pointing to.
*/
case OP_VColumn: {
  break;
}
#endif /* SQLITE_OMIT_VIRTUALTABLE */

#ifndef SQLITE_OMIT_VIRTUALTABLE
/* Opcode: VNext P1 P2 *
**
** Advance virtual table P1 to the next row in its result set and
** jump to instruction P2.  Or, if the virtual table has reached
** the end of its result set, then fall through to the next instruction.
*/
case OP_VNext: {
  break;
}
#endif /* SQLITE_OMIT_VIRTUALTABLE */

/* An other opcode is illegal...
*/
default: {
  assert( 0 );

  int nData;            /* Number of bytes in pData */
  char *pData;          /* Data for a NEW or OLD pseudo-table */
  i64 iKey;             /* Key for the NEW or OLD pseudo-table row */
  u8 *pIncrKey;         /* Pointer to pKeyInfo->incrKey */
  KeyInfo *pKeyInfo;    /* Info about index keys needed by index cursors */
  int nField;           /* Number of fields in the header */
  i64 seqCount;         /* Sequence counter */




  /* Cached information about the header for the data record that the
  ** cursor is currently pointing to.  Only valid if cacheValid is true.
  ** aRow might point to (ephemeral) data for the current row, or it might
  ** be NULL.
  */
  int cacheStatus;      /* Cache is valid if this matches Vdbe.cacheCtr */

  int nData;            /* Number of bytes in pData */
  char *pData;          /* Data for a NEW or OLD pseudo-table */
  i64 iKey;             /* Key for the NEW or OLD pseudo-table row */
  u8 *pIncrKey;         /* Pointer to pKeyInfo->incrKey */
  KeyInfo *pKeyInfo;    /* Info about index keys needed by index cursors */
  int nField;           /* Number of fields in the header */
  i64 seqCount;         /* Sequence counter */
#ifndef SQLITE_OMIT_VIRTUALTABLE
  sqlite3_vtab_cursor *pVtabCursor;  /* The cursor for a virtual table */
#endif

  /* Cached information about the header for the data record that the
  ** cursor is currently pointing to.  Only valid if cacheValid is true.
  ** aRow might point to (ephemeral) data for the current row, or it might
  ** be NULL.
  */
  int cacheStatus;      /* Cache is valid if this matches Vdbe.cacheCtr */

  }
  if( pCx->pCursor ){
    sqlite3BtreeCloseCursor(pCx->pCursor);
  }
  if( pCx->pBt ){
    sqlite3BtreeClose(pCx->pBt);
  }








  sqliteFree(pCx->pData);
  sqliteFree(pCx->aType);
  sqliteFree(pCx);
}

/*
** Close all cursors

  }
  if( pCx->pCursor ){
    sqlite3BtreeCloseCursor(pCx->pCursor);
  }
  if( pCx->pBt ){
    sqlite3BtreeClose(pCx->pBt);
  }
#ifndef SQLITE_OMIT_VIRTUALTABLE
  if( pCx->pVtabCursor ){
    sqlite3_vtab_cursor *pVtabCursor = pCx->pVtabCursor;
    sqlite3_vtab *pVtab = pVtabCursor->pVtab;
    sqlite3_module *pModule = pVtab->pModule;
    pModule->xClose(pVtabCursor);
  }
#endif
  sqliteFree(pCx->pData);
  sqliteFree(pCx->aType);
  sqliteFree(pCx);
}

/*
** Close all cursors

** 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.210 2006/06/11 23:41:56 drh Exp $
*/
#include "sqliteInt.h"

/*
** The number of bits in a Bitmask.  "BMS" means "BitMask Size".
*/
#define BMS  (sizeof(Bitmask)*8)
................................................................................
#define WHERE_COLUMN_IN      0x0040   /* x IN (...) */
#define WHERE_TOP_LIMIT      0x0100   /* x<EXPR or x<=EXPR constraint */
#define WHERE_BTM_LIMIT      0x0200   /* x>EXPR or x>=EXPR constraint */
#define WHERE_IDX_ONLY       0x0800   /* Use index only - omit table */
#define WHERE_ORDERBY        0x1000   /* Output will appear in correct order */
#define WHERE_REVERSE        0x2000   /* Scan in reverse order */
#define WHERE_UNIQUE         0x4000   /* Selects no more than one row */


/*
** Initialize a preallocated WhereClause structure.
*/
static void whereClauseInit(WhereClause *pWC, Parse *pParse){
  pWC->pParse = pParse;
  pWC->nTerm = 0;
................................................................................
  while( N>x ){
    logN += 1;
    x *= 10;
  }
  return logN;
}






































































































































/*
** Find the best index for accessing a particular table.  Return a pointer
** to the index, flags that describe how the index should be used, the
** number of equality constraints, and the "cost" for this index.
**
** The lowest cost index wins.  The cost is an estimate of the amount of
** CPU and disk I/O need to process the request using the selected index.
................................................................................
*/
char sqlite3_query_plan[BMS*2*40];  /* Text of the join */
static int nQPlan = 0;              /* Next free slow in _query_plan[] */

#endif /* SQLITE_TEST */
















/*
** Generate the beginning of the loop used for WHERE clause processing.
** The return value is a pointer to an opaque structure that contains
** information needed to terminate the loop.  Later, the calling routine
** should invoke sqlite3WhereEnd() with the return value of this function
** in order to complete the WHERE clause processing.
................................................................................
                   || (j>0 && (pTabItem[-1].jointype & (JT_LEFT|JT_CROSS))!=0);
      if( once && doNotReorder ) break;
      m = getMask(&maskSet, pTabItem->iCursor);
      if( (m & notReady)==0 ){
        if( j==iFrom ) iFrom++;
        continue;
      }












      cost = bestIndex(pParse, &wc, pTabItem, notReady,
                       (i==0 && ppOrderBy) ? *ppOrderBy : 0,
                       &pIdx, &flags, &nEq);

      if( cost<lowestCost ){
        once = 1;
        lowestCost = cost;
        pBest = pIdx;
        bestFlags = flags;
        bestNEq = nEq;
        bestJ = j;
................................................................................
        zMsg = sqlite3MPrintf("%z AS %s", zMsg, pItem->zAlias);
      }
      if( (pIx = pLevel->pIdx)!=0 ){
        zMsg = sqlite3MPrintf("%z WITH INDEX %s", zMsg, pIx->zName);
      }else if( pLevel->flags & (WHERE_ROWID_EQ|WHERE_ROWID_RANGE) ){
        zMsg = sqlite3MPrintf("%z USING PRIMARY KEY", zMsg);
      }






      if( pLevel->flags & WHERE_ORDERBY ){
        zMsg = sqlite3MPrintf("%z ORDER BY", zMsg);
      }
      sqlite3VdbeOp3(v, OP_Explain, i, pLevel->iFrom, zMsg, P3_DYNAMIC);
    }
#endif /* SQLITE_OMIT_EXPLAIN */
    pTabItem = &pTabList->a[pLevel->iFrom];
    pTab = pTabItem->pTab;
    iDb = sqlite3SchemaToIndex(pParse->db, pTab->pSchema);
    if( pTab->isEphem || pTab->pSelect ) continue;





    if( (pLevel->flags & WHERE_IDX_ONLY)==0 ){
      sqlite3OpenTable(pParse, pTabItem->iCursor, iDb, pTab, OP_OpenRead);
      if( pTab->nCol<(sizeof(Bitmask)*8) ){
        Bitmask b = pTabItem->colUsed;
        int n = 0;
        for(; b; b=b>>1, n++){}
        sqlite3VdbeChangeP2(v, sqlite3VdbeCurrentAddr(v)-1, n);
................................................................................
    if( pLevel->iFrom>0 && (pTabItem[-1].jointype & JT_LEFT)!=0 ){
      if( !pParse->nMem ) pParse->nMem++;
      pLevel->iLeftJoin = pParse->nMem++;
      sqlite3VdbeAddOp(v, OP_MemInt, 0, pLevel->iLeftJoin);
      VdbeComment((v, "# init LEFT JOIN no-match flag"));
    }





























    if( pLevel->flags & WHERE_ROWID_EQ ){
      /* Case 1:  We can directly reference a single row using an
      **          equality comparison against the ROWID field.  Or
      **          we reference multiple rows using a "rowid IN (...)"
      **          construct.
      */
      pTerm = findTerm(&wc, iCur, -1, notReady, WO_EQ|WO_IN, 0);
................................................................................
  pWInfo->iContinue = cont;
  whereClauseClear(&wc);
  return pWInfo;

  /* Jump here if malloc fails */
whereBeginNoMem:
  whereClauseClear(&wc);
  sqliteFree(pWInfo);
  return 0;
}

/*
** Generate the end of the WHERE loop.  See comments on 
** sqlite3WhereBegin() for additional information.
*/
................................................................................
        }
      }
    }
  }

  /* Final cleanup
  */
  sqliteFree(pWInfo);
  return;
}

** 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.211 2006/06/12 21:59:14 drh Exp $
*/
#include "sqliteInt.h"

/*
** The number of bits in a Bitmask.  "BMS" means "BitMask Size".
*/
#define BMS  (sizeof(Bitmask)*8)
................................................................................
#define WHERE_COLUMN_IN      0x0040   /* x IN (...) */
#define WHERE_TOP_LIMIT      0x0100   /* x<EXPR or x<=EXPR constraint */
#define WHERE_BTM_LIMIT      0x0200   /* x>EXPR or x>=EXPR constraint */
#define WHERE_IDX_ONLY       0x0800   /* Use index only - omit table */
#define WHERE_ORDERBY        0x1000   /* Output will appear in correct order */
#define WHERE_REVERSE        0x2000   /* Scan in reverse order */
#define WHERE_UNIQUE         0x4000   /* Selects no more than one row */
#define WHERE_VIRTUALTABLE   0x8000   /* Use virtual-table processing */

/*
** Initialize a preallocated WhereClause structure.
*/
static void whereClauseInit(WhereClause *pWC, Parse *pParse){
  pWC->pParse = pParse;
  pWC->nTerm = 0;
................................................................................
  while( N>x ){
    logN += 1;
    x *= 10;
  }
  return logN;
}

#ifndef SQLITE_OMIT_VIRTUALTABLE
/*
** Compute the best index for a virtual table
*/
static double bestVirtualIndex(
  Parse *pParse,                 /* The parsing context */
  WhereClause *pWC,              /* The WHERE clause */
  struct SrcList_item *pSrc,     /* The FROM clause term to search */
  Bitmask notReady,              /* Mask of cursors that are not available */
  ExprList *pOrderBy,            /* The order by clause */
  int orderByUsable,             /* True if we can potential sort */
  sqlite3_index_info **ppIdxInfo /* Index information passed to xBestIndex */
){
  Table *pTab = pSrc->pTab;
  sqlite3_index_info *pIdxInfo;
  struct sqlite3_index_constraint *pIdxCons;
  struct sqlite3_index_orderby *pIdxOrderBy;
  struct sqlite3_index_constraint_usage *pUsage;
  WhereTerm *pTerm;
  int i, j;
  int nOrderBy;

  /* If the sqlite3_index_info structure has not been previously
  ** allocated and initialized for this virtual table, then allocate
  ** and initialize it now
  */
  pIdxInfo = *ppIdxInfo;
  if( pIdxInfo==0 ){
    WhereTerm *pTerm;
    int nTerm;

    /* Count the number of possible WHERE clause constraints referring
    ** to this virtual table */
    for(i=nTerm=0, pTerm=pWC->a; i<pWC->nTerm; i++, pTerm++){
      if( pTerm->leftCursor != pSrc->iCursor ) continue;
      if( pTerm->eOperator==WO_IN ) continue;
      nTerm++;
    }

    /* If the ORDER BY clause contains only columns in the current 
    ** virtual table then allocate space for the aOrderBy part of
    ** the sqlite3_index_info structure.
    */
    nOrderBy = 0;
    if( pOrderBy ){
      for(i=0; i<pOrderBy->nExpr; i++){
        Expr *pExpr = pOrderBy->a[i].pExpr;
        if( pExpr->op!=TK_COLUMN || pExpr->iTable!=pSrc->iCursor ) break;
      }
      if( i==pOrderBy->nExpr ){
        nOrderBy = pOrderBy->nExpr;
      }
    }

    /* Allocate the sqlite3_index_info structure
    */
    pIdxInfo = sqliteMalloc( sizeof(*pIdxInfo)
                             + (sizeof(*pIdxCons) + sizeof(*pUsage))*nTerm
                             + sizeof(*pIdxOrderBy)*nOrderBy );
    if( pIdxInfo==0 ){
      sqlite3ErrorMsg(pParse, "out of memory");
      return 0.0;
    }
    *ppIdxInfo = pIdxInfo;

    /* Initialize the structure.  The sqlite3_index_info structure contains
    ** many fields that are declared "const" to prevent xBestIndex from
    ** changing them.  We have to do some funky casting in order to
    ** initialize those fields.
    */
    pIdxCons = (struct sqlite3_index_constraint*)&pIdxInfo[1];
    pIdxOrderBy = (struct sqlite3_index_orderby*)&pIdxCons[nTerm];
    pUsage = (struct sqlite3_index_constraint_usage*)&pIdxOrderBy[nOrderBy];
    *(int*)&pIdxInfo->nConstraint = nTerm;
    *(int*)&pIdxInfo->nOrderBy = nOrderBy;
    *(struct sqlite3_index_constraint**)&pIdxInfo->aConstraint = pIdxCons;
    *(struct sqlite3_index_orderby**)&pIdxInfo->aOrderBy = pIdxOrderBy;
    *(struct sqlite3_index_constraint_usage**)&pIdxInfo->aConstraintUsage =
                                                                     pUsage;

    for(i=j=0, pTerm=pWC->a; i<pWC->nTerm; i++, pTerm++){
      if( pTerm->leftCursor != pSrc->iCursor ) continue;
      if( pTerm->eOperator==WO_IN ) continue;
      pIdxCons[j].iColumn = pTerm->leftColumn;
      pIdxCons[j].iTermOffset = i;
      pIdxCons[j].op = pTerm->eOperator;
      assert( WO_EQ==SQLITE_INDEX_CONSTRAINT_EQ );
      assert( WO_LT==SQLITE_INDEX_CONSTRAINT_LT );
      assert( WO_LE==SQLITE_INDEX_CONSTRAINT_LE );
      assert( WO_GT==SQLITE_INDEX_CONSTRAINT_GT );
      assert( WO_GE==SQLITE_INDEX_CONSTRAINT_GE );
      assert( pTerm->eOperator & (WO_EQ|WO_LT|WO_LE|WO_GT|WO_GE) );
      j++;
    }
    for(i=0; i<nOrderBy; i++){
      Expr *pExpr = pOrderBy->a[i].pExpr;
      pIdxOrderBy[i].iColumn = pExpr->iColumn;
      pIdxOrderBy[i].desc = pOrderBy->a[i].sortOrder;
    }
  }

  /* The module name must be defined */
  assert( pTab->azModuleArg && pTab->azModuleArg[0] );
  if( pTab->pVtab==0 ){
    sqlite3ErrorMsg(pParse, "undefined module %s for table %s",
        pTab->azModuleArg[0], pTab->zName);
    return 0.0;
  }

  /* Set the aConstraint[].usable fields and initialize all 
  ** output variables
  */
  pIdxCons = *(struct sqlite3_index_constraint**)&pIdxInfo->aConstraint;
  pUsage = pIdxInfo->aConstraintUsage;
  for(i=0; i<pIdxInfo->nConstraint; i++, pIdxCons++){
    j = pIdxCons->iTermOffset;
    pTerm = &pWC->a[j];
    pIdxCons->usable =  (pTerm->prereqRight & notReady)==0;
  }
  memset(pUsage, 0, sizeof(pUsage[0])*pIdxInfo->nConstraint);
  pIdxInfo->idxNum = 0;
  pIdxInfo->orderByConsumed = 0;
  pIdxInfo->estimatedCost = SQLITE_BIG_DBL;
  nOrderBy = pIdxInfo->nOrderBy;
  if( pIdxInfo->nOrderBy && !orderByUsable ){
    *(int*)pIdxInfo->nOrderBy = 0;
  }
  pTab->pVtab->pModule->xBestIndex(pTab->pVtab, pIdxInfo);
  *(int*)pIdxInfo->nOrderBy = nOrderBy;
  return pIdxInfo->estimatedCost;
}
#endif /* SQLITE_OMIT_VIRTUALTABLE */

/*
** Find the best index for accessing a particular table.  Return a pointer
** to the index, flags that describe how the index should be used, the
** number of equality constraints, and the "cost" for this index.
**
** The lowest cost index wins.  The cost is an estimate of the amount of
** CPU and disk I/O need to process the request using the selected index.
................................................................................
*/
char sqlite3_query_plan[BMS*2*40];  /* Text of the join */
static int nQPlan = 0;              /* Next free slow in _query_plan[] */

#endif /* SQLITE_TEST */


/*
** Free a WhereInfo structure
*/
static void whereInfoFree(WhereInfo *pWInfo){
  if( pWInfo ){
    int i;
    for(i=0; i<pWInfo->nLevel; i++){
      sqliteFree(pWInfo->a[i].pIdxInfo);
    }
    sqliteFree(pWInfo);
  }
}


/*
** Generate the beginning of the loop used for WHERE clause processing.
** The return value is a pointer to an opaque structure that contains
** information needed to terminate the loop.  Later, the calling routine
** should invoke sqlite3WhereEnd() with the return value of this function
** in order to complete the WHERE clause processing.
................................................................................
                   || (j>0 && (pTabItem[-1].jointype & (JT_LEFT|JT_CROSS))!=0);
      if( once && doNotReorder ) break;
      m = getMask(&maskSet, pTabItem->iCursor);
      if( (m & notReady)==0 ){
        if( j==iFrom ) iFrom++;
        continue;
      }
      assert( pTabItem->pTab );
#ifndef SQLITE_OMIT_VIRTUALTABLE
      if( pTabItem->pTab->isVirtual ){
        cost = bestVirtualIndex(pParse, &wc, pTabItem, notReady,
                                ppOrderBy ? *ppOrderBy : 0, i==0,
                                &pLevel->pIdxInfo);
        flags = WHERE_VIRTUALTABLE;
        pIdx = 0;
        nEq = 0;
      }else 
#endif
      {
        cost = bestIndex(pParse, &wc, pTabItem, notReady,
                         (i==0 && ppOrderBy) ? *ppOrderBy : 0,
                         &pIdx, &flags, &nEq);
      }
      if( cost<lowestCost ){
        once = 1;
        lowestCost = cost;
        pBest = pIdx;
        bestFlags = flags;
        bestNEq = nEq;
        bestJ = j;
................................................................................
        zMsg = sqlite3MPrintf("%z AS %s", zMsg, pItem->zAlias);
      }
      if( (pIx = pLevel->pIdx)!=0 ){
        zMsg = sqlite3MPrintf("%z WITH INDEX %s", zMsg, pIx->zName);
      }else if( pLevel->flags & (WHERE_ROWID_EQ|WHERE_ROWID_RANGE) ){
        zMsg = sqlite3MPrintf("%z USING PRIMARY KEY", zMsg);
      }
#ifndef SQLITE_OMIT_VIRTUALTABLE
      else if( pLevel->pIdxInfo ){
        zMsg = sqlite3MPrintf("%z VIRTUAL TABLE INDEX %d",
                    pLevel->pIdxInfo->idxNum);
      }
#endif
      if( pLevel->flags & WHERE_ORDERBY ){
        zMsg = sqlite3MPrintf("%z ORDER BY", zMsg);
      }
      sqlite3VdbeOp3(v, OP_Explain, i, pLevel->iFrom, zMsg, P3_DYNAMIC);
    }
#endif /* SQLITE_OMIT_EXPLAIN */
    pTabItem = &pTabList->a[pLevel->iFrom];
    pTab = pTabItem->pTab;
    iDb = sqlite3SchemaToIndex(pParse->db, pTab->pSchema);
    if( pTab->isEphem || pTab->pSelect ) continue;
#ifndef SQLITE_OMIT_VIRTUALTABLE
    if( pLevel->pIdxInfo ){
      sqlite3VdbeAddOp(v, OP_VOpen, 0, 0);  /***** Fix Me *****/
    }else
#endif
    if( (pLevel->flags & WHERE_IDX_ONLY)==0 ){
      sqlite3OpenTable(pParse, pTabItem->iCursor, iDb, pTab, OP_OpenRead);
      if( pTab->nCol<(sizeof(Bitmask)*8) ){
        Bitmask b = pTabItem->colUsed;
        int n = 0;
        for(; b; b=b>>1, n++){}
        sqlite3VdbeChangeP2(v, sqlite3VdbeCurrentAddr(v)-1, n);
................................................................................
    if( pLevel->iFrom>0 && (pTabItem[-1].jointype & JT_LEFT)!=0 ){
      if( !pParse->nMem ) pParse->nMem++;
      pLevel->iLeftJoin = pParse->nMem++;
      sqlite3VdbeAddOp(v, OP_MemInt, 0, pLevel->iLeftJoin);
      VdbeComment((v, "# init LEFT JOIN no-match flag"));
    }

#ifndef SQLITE_OMIT_VIRTUALTABLE
    if( pLevel->pIdxInfo ){
      /* Case 0:  That table is a virtual-table.  Use the VFilter and VNext.
      */
      sqlite3_index_info *pIdxInfo = pLevel->pIdxInfo;
      for(i=1; i<=pIdxInfo->nConstraint; i++){
        int j;
        for(j=0; j<pIdxInfo->nConstraint; j++){
          if( pIdxInfo->aConstraintUsage[j].argvIndex==i ){
            sqlite3ExprCode(pParse, wc.a[j].pExpr->pRight);
            break;
          }
        }
        if( j==pIdxInfo->nConstraint ) break;
      }
      sqlite3VdbeAddOp(v, OP_VFilter, iCur, pIdxInfo->idxNum);
      if( i>1 ){
        sqlite3VdbeAddOp(v, OP_Pop, i-1, 0);
      }
      for(i=0; i<pIdxInfo->nConstraint; i++){
        if( pIdxInfo->aConstraintUsage[i].omit ){
          disableTerm(pLevel, &wc.a[i]);
        }
      }
      pLevel->op = OP_VNext;
    }else
#endif /* SQLITE_OMIT_VIRTUALTABLE */

    if( pLevel->flags & WHERE_ROWID_EQ ){
      /* Case 1:  We can directly reference a single row using an
      **          equality comparison against the ROWID field.  Or
      **          we reference multiple rows using a "rowid IN (...)"
      **          construct.
      */
      pTerm = findTerm(&wc, iCur, -1, notReady, WO_EQ|WO_IN, 0);
................................................................................
  pWInfo->iContinue = cont;
  whereClauseClear(&wc);
  return pWInfo;

  /* Jump here if malloc fails */
whereBeginNoMem:
  whereClauseClear(&wc);
  whereInfoFree(pWInfo);
  return 0;
}

/*
** Generate the end of the WHERE loop.  See comments on 
** sqlite3WhereBegin() for additional information.
*/
................................................................................
        }
      }
    }
  }

  /* Final cleanup
  */
  whereInfoFree(pWInfo);
  return;
}