SQLite

} {
  SELECT * FROM t1 ORDER BY a, b, c;
} {
  CREATE INDEX t1_idx_033e95fe ON t1(a, b, c);
  0|0|0|SCAN TABLE t1 USING COVERING INDEX t1_idx_033e95fe
}

do_setup_rec_test $tn.1.8 {
  CREATE TABLE t1(a, b, c);
} {
  SELECT * FROM t1 ORDER BY a ASC, b COLLATE nocase DESC, c ASC;
} {
  CREATE INDEX t1_idx_5be6e222 ON t1(a, b COLLATE NOCASE DESC, c);
  0|0|0|SCAN TABLE t1 USING COVERING INDEX t1_idx_5be6e222
}


do_setup_rec_test $tn.1.9 {
  CREATE TABLE t1(a COLLATE NOCase, b, c);
} {
  SELECT * FROM t1 WHERE a=?
} {
  CREATE INDEX t1_idx_00000061 ON t1(a);
  0|0|0|SEARCH TABLE t1 USING INDEX t1_idx_00000061 (a=?)
}











# Tables with names that require quotes.
#
do_setup_rec_test $tn.8.1 {
  CREATE TABLE "t t"(a, b, c);
} {

  IdxConstraint *pLink;           /* See above */
};

/*
** A single scan of a single table.
*/
struct IdxScan {
  char *zTable;                   /* Name of table to scan */
  int iDb;                        /* Database containing table zTable */
  i64 covering;                   /* Mask of columns required for cov. index */
  IdxConstraint *pOrder;          /* ORDER BY columns */
  IdxConstraint *pEq;             /* List of == constraints */
  IdxConstraint *pRange;          /* List of < constraints */
  IdxScan *pNextScan;             /* Next IdxScan object for same analysis */
};

/*
** Information regarding a single database table. Extracted from 
** "PRAGMA table_info" by function idxGetTableInfo().
*/
struct IdxColumn {
  char *zName;
  char *zColl;
  int iPk;
};
struct IdxTable {
  int nCol;

  IdxColumn *aCol;

};

/*
** Each statement being analyzed is represented by an instance of this
** structure.
*/
struct IdxStatement {

/*
** sqlite3expert object.
*/
struct sqlite3expert {
  sqlite3 *db;                    /* User database */
  sqlite3 *dbm;                   /* In-memory db for this analysis */



  IdxScan *pScan;                 /* List of scan objects */
  IdxStatement *pStatement;       /* List of IdxStatement objects */
  int bRun;                       /* True once analysis has run */
  char **pzErrmsg;
  int rc;                         /* Error code from whereinfo hook */
  IdxHash hIdx;                   /* Hash containing all candidate indexes */
  char *zCandidates;              /* For EXPERT_REPORT_CANDIDATES */

  if( pNew ){
    pNew->zColl = (char*)&pNew[1];
    memcpy(pNew->zColl, zColl, nColl+1);
  }
  return pNew;
}

/*
** sqlite3_whereinfo_hook() callback.

*/


static void idxWhereInfo(

  void *pCtx,                     /* Pointer to sqlite3expert structure */

  int eOp, 
  const char *zVal, 
  int iVal, 
  u64 mask
){
  sqlite3expert *p = (sqlite3expert*)pCtx;


#if 0

  const char *zOp = 









    eOp==SQLITE_WHEREINFO_TABLE ? "TABLE" :


    eOp==SQLITE_WHEREINFO_EQUALS ? "EQUALS" :
    eOp==SQLITE_WHEREINFO_RANGE ? "RANGE" :
    eOp==SQLITE_WHEREINFO_ORDERBY ? "ORDERBY" :









    "!error!";
  printf("op=%s zVal=%s iVal=%d mask=%llx\n", zOp, zVal, iVal, mask);
#endif
















  if( p->rc==SQLITE_OK ){


    assert( eOp==SQLITE_WHEREINFO_TABLE || p->pScan!=0 );




    switch( eOp ){

      case SQLITE_WHEREINFO_TABLE: {


        int nVal = strlen(zVal);
        IdxScan *pNew = (IdxScan*)idxMalloc(&p->rc, sizeof(IdxScan) + nVal + 1);

        if( !pNew ) return;

        pNew->zTable = (char*)&pNew[1];
        memcpy(pNew->zTable, zVal, nVal+1);
        pNew->pNextScan = p->pScan;
        pNew->covering = mask;

        p->pScan = pNew;
        break;

      }















      case SQLITE_WHEREINFO_ORDERBY: {









        IdxConstraint *pNew = idxNewConstraint(&p->rc, zVal);


        if( pNew==0 ) return;
        pNew->iCol = iVal;
        pNew->bDesc = (int)mask;

        if( p->pScan->pOrder==0 ){
          p->pScan->pOrder = pNew;
        }else{
          IdxConstraint *pIter;
          for(pIter=p->pScan->pOrder; pIter->pNext; pIter=pIter->pNext);

          pIter->pNext = pNew;
          pIter->pLink = pNew;
        }
        break;
      }






      case SQLITE_WHEREINFO_EQUALS:
      case SQLITE_WHEREINFO_RANGE: {


        IdxConstraint *pNew = idxNewConstraint(&p->rc, zVal);


        if( pNew==0 ) return;
        pNew->iCol = iVal;
        pNew->depmask = mask;

        if( eOp==SQLITE_WHEREINFO_RANGE ){
          pNew->pNext = p->pScan->pRange;
          p->pScan->pRange = pNew;
        }else{
          pNew->pNext = p->pScan->pEq;
          p->pScan->pEq = pNew;

        }


        break;


      }
    }


























  }

}




/*
** An error associated with database handle db has just occurred. Pass
** the error message to callback function xOut.
*/
static void idxDatabaseError(
  sqlite3 *db,                    /* Database handle */

  sqlite3 *db,                    /* Database connection to read details from */
  const char *zTab,               /* Table name */
  IdxTable **ppOut,               /* OUT: New object (if successful) */
  char **pzErrmsg                 /* OUT: Error message (if not) */
){
  sqlite3_stmt *p1 = 0;
  int nCol = 0;

  int nByte = sizeof(IdxTable);
  IdxTable *pNew = 0;
  int rc, rc2;
  char *pCsr;

  rc = idxPrintfPrepareStmt(db, &p1, pzErrmsg, "PRAGMA table_info=%Q", zTab);
  while( rc==SQLITE_OK && SQLITE_ROW==sqlite3_step(p1) ){
    const char *zCol = (const char*)sqlite3_column_text(p1, 1);

    nCol++;
  }
  idxFinalize(&rc, p1);

  if( rc!=SQLITE_OK ){
    sqlite3_free(pNew);
    pNew = 0;



  }

  *ppOut = pNew;
  return rc;
}

/*

static int idxFindCompatible(
  int *pRc,                       /* OUT: Error code */
  sqlite3* dbm,                   /* Database to search */
  IdxScan *pScan,                 /* Scan for table to search for index on */
  IdxConstraint *pEq,             /* List of == constraints */
  IdxConstraint *pTail            /* List of range constraints */
){
  const char *zTbl = pScan->zTable;
  sqlite3_stmt *pIdxList = 0;
  IdxConstraint *pIter;
  int nEq = 0;                    /* Number of elements in pEq */
  int rc;

  /* Count the elements in list pEq */
  for(pIter=pEq; pIter; pIter=pIter->pLink) nEq++;

    }
    for(pCons=pTail; pCons; pCons=pCons->pLink){
      zCols = idxAppendColDefn(&rc, zCols, pTab, pCons);
    }

    if( rc==SQLITE_OK ){
      /* Hash the list of columns to come up with a name for the index */

      char *zName;                /* Index name */
      int i;
      for(i=0; zCols[i]; i++){
        h += ((h<<3) + zCols[i]);
      }
      zName = sqlite3_mprintf("%s_idx_%08x", pScan->zTable, h);
      if( zName==0 ){ 
        rc = SQLITE_NOMEM;
      }else{
        if( idxIdentifierRequiresQuotes(pScan->zTable) ){
          zFmt = "CREATE INDEX '%q' ON %Q(%s)";
        }else{
          zFmt = "CREATE INDEX %s ON %s(%s)";
        }
        zIdx = sqlite3_mprintf(zFmt, zName, pScan->zTable, zCols);
        if( !zIdx ){
          rc = SQLITE_NOMEM;
        }else{
          rc = sqlite3_exec(dbm, zIdx, 0, 0, p->pzErrmsg);
          idxHashAdd(&rc, &p->hIdx, zName, zIdx);
        }
        sqlite3_free(zName);

  IdxScan *pIter;
  IdxHash64 hMask;
  idxHash64Init(&hMask);

  for(pIter=p->pScan; pIter && rc==SQLITE_OK; pIter=pIter->pNextScan){
    IdxHash64Entry *pEntry;
    IdxConstraint *pCons;
    IdxTable *pTab = 0;

    rc = idxGetTableInfo(p->dbm, pIter->zTable, &pTab, pzErr);

    idxHash64Add(&rc, &hMask, 0);
    for(pCons=pIter->pEq; pCons; pCons=pCons->pNext){
      for(pEntry=hMask.pFirst; pEntry; pEntry=pEntry->pNext){
        idxHash64Add(&rc, &hMask, pEntry->iVal | (u64)pCons->depmask);
      }
    }

    for(pEntry=hMask.pFirst; rc==SQLITE_OK && pEntry; pEntry=pEntry->pNext){
      i64 mask = (i64)pEntry->iVal;
      rc = idxCreateFromWhere(p, pTab, mask, pIter, 0, 0);
      if( rc==SQLITE_OK && pIter->pOrder ){
        rc = idxCreateFromWhere(p, pTab, mask, pIter, 0, pIter->pOrder);
      }
    }

    sqlite3_free(pTab);
    idxHash64Clear(&hMask);
  }

  return rc;
}

/*

    idxFinalize(&rc, pExplain);
  }

 find_indexes_out:
  idxHashClear(&hIdx);
  return rc;
}























































/*
** Allocate a new sqlite3expert object.
*/
sqlite3expert *sqlite3_expert_new(sqlite3 *db, char **pzErrmsg){
  int rc = SQLITE_OK;
  sqlite3expert *pNew;

  pNew = (sqlite3expert*)idxMalloc(&rc, sizeof(sqlite3expert));








  pNew->db = db;


  /* Open an in-memory database to work with. The main in-memory 
  ** database schema contains tables similar to those in the users 
  ** database (handle db).  */

  rc = sqlite3_open(":memory:", &pNew->dbm);


  /* Copy the entire schema of database [db] into [dbm]. */
  if( rc==SQLITE_OK ){
    sqlite3_stmt *pSql;
    rc = idxPrintfPrepareStmt(pNew->db, &pSql, pzErrmsg, 
        "SELECT sql FROM sqlite_master WHERE name NOT LIKE 'sqlite_%%'"
    );
    while( rc==SQLITE_OK && SQLITE_ROW==sqlite3_step(pSql) ){
      const char *zSql = (const char*)sqlite3_column_text(pSql, 0);
      rc = sqlite3_exec(pNew->dbm, zSql, 0, 0, pzErrmsg);
    }
    idxFinalize(&rc, pSql);
  }






  /* If an error has occurred, free the new object and reutrn NULL. Otherwise,
  ** return the new sqlite3expert handle.  */
  if( rc!=SQLITE_OK ){
    sqlite3_expert_destroy(pNew);
    pNew = 0;
  }

  IdxScan *pScanOrig = p->pScan;
  IdxStatement *pStmtOrig = p->pStatement;
  int rc = SQLITE_OK;
  const char *zStmt = zSql;

  if( p->bRun ) return SQLITE_MISUSE;

  sqlite3_whereinfo_hook(p->db, idxWhereInfo, p);
  while( rc==SQLITE_OK && zStmt && zStmt[0] ){
    sqlite3_stmt *pStmt = 0;
    rc = sqlite3_prepare_v2(p->db, zStmt, -1, &pStmt, &zStmt);
    if( rc==SQLITE_OK ){
      if( pStmt ){
        IdxStatement *pNew;
        const char *z = sqlite3_sql(pStmt);
        int n = strlen(z);
        pNew = (IdxStatement*)idxMalloc(&rc, sizeof(IdxStatement) + n+1);
        if( rc==SQLITE_OK ){
          pNew->zSql = (char*)&pNew[1];
          memcpy(pNew->zSql, z, n+1);
          pNew->pNext = p->pStatement;
          if( p->pStatement ) pNew->iId = p->pStatement->iId+1;
          p->pStatement = pNew;
        }
        sqlite3_finalize(pStmt);
      }
    }else{
      idxDatabaseError(p->db, pzErr);
    }
  }
  sqlite3_whereinfo_hook(p->db, 0, 0);

  if( rc!=SQLITE_OK ){
    idxScanFree(p->pScan, pScanOrig);
    idxStatementFree(p->pStatement, pStmtOrig);
    p->pScan = pScanOrig;
    p->pStatement = pStmtOrig;
  }

  return rc;
}

int sqlite3_expert_analyze(sqlite3expert *p, char **pzErr){
  int rc;
  IdxHashEntry *pEntry;

  /* Create candidate indexes within the in-memory database file */
  rc = idxCreateCandidates(p, pzErr);


  for(pEntry=p->hIdx.pFirst; pEntry; pEntry=pEntry->pNext){
    p->zCandidates = idxAppendText(&rc, p->zCandidates, "%s;\n", pEntry->zVal);
  }

  /* Figure out which of the candidate indexes are preferred by the query
  ** planner and report the results to the user.  */
  if( rc==SQLITE_OK ){

  return zRet;
}

/*
** Free an sqlite3expert object.
*/
void sqlite3_expert_destroy(sqlite3expert *p){

  sqlite3_close(p->dbm);

  idxScanFree(p->pScan, 0);
  idxStatementFree(p->pStatement, 0);
  idxHashClear(&p->hIdx);
  sqlite3_free(p);

}

#endif /* !defined(SQLITE_TEST) || defined(SQLITE_ENABLE_WHEREINFO_HOOK) */

  pRet = db->pPreUpdateArg;
  db->xPreUpdateCallback = xCallback;
  db->pPreUpdateArg = pArg;
  sqlite3_mutex_leave(db->mutex);
  return pRet;
}
#endif /* SQLITE_ENABLE_PREUPDATE_HOOK */

#ifdef SQLITE_ENABLE_WHEREINFO_HOOK
/*
** Register a where-info hook.
*/
void *sqlite3_whereinfo_hook(
  sqlite3 *db,                    /* Register callback with this db handle */
  void (*xWhereInfo)(void*, int, const char*, int, sqlite3_uint64),
  void *pCtx                      /* User pointer passed to callback */
){
  void *pRet;
  sqlite3_mutex_enter(db->mutex);
  pRet = db->pWhereInfoCtx;
  db->xWhereInfo = xWhereInfo;
  db->pWhereInfoCtx = pCtx;
  sqlite3_mutex_leave(db->mutex);
  return pRet;
}
#endif /* SQLITE_ENABLE_WHEREINFO_HOOK */


#ifndef SQLITE_OMIT_WAL
/*
** The sqlite3_wal_hook() callback registered by sqlite3_wal_autocheckpoint().
** Invoke sqlite3_wal_checkpoint if the number of frames in the log file
** is greater than sqlite3.pWalArg cast to an integer (the value configured by
** wal_autocheckpoint()).

#define SQLITE_DBCONFIG_MAINDBNAME            1000 /* const char* */
#define SQLITE_DBCONFIG_LOOKASIDE             1001 /* void* int int */
#define SQLITE_DBCONFIG_ENABLE_FKEY           1002 /* int int* */
#define SQLITE_DBCONFIG_ENABLE_TRIGGER        1003 /* int int* */
#define SQLITE_DBCONFIG_ENABLE_FTS3_TOKENIZER 1004 /* int int* */
#define SQLITE_DBCONFIG_ENABLE_LOAD_EXTENSION 1005 /* int int* */
#define SQLITE_DBCONFIG_NO_CKPT_ON_CLOSE      1006 /* int int* */


/*
** CAPI3REF: Enable Or Disable Extended Result Codes
** METHOD: sqlite3
**
** ^The sqlite3_extended_result_codes() routine enables or disables the
** [extended result codes] feature of SQLite. ^The extended result

** value returned is one of [SQLITE_ROLLBACK], [SQLITE_IGNORE], [SQLITE_FAIL],
** [SQLITE_ABORT], or [SQLITE_REPLACE], according to the [ON CONFLICT] mode
** of the SQL statement that triggered the call to the [xUpdate] method of the
** [virtual table].
*/
int sqlite3_vtab_on_conflict(sqlite3 *);



/*
** CAPI3REF: Conflict resolution modes
** KEYWORDS: {conflict resolution mode}
**
** These constants are returned by [sqlite3_vtab_on_conflict()] to
** inform a [virtual table] implementation what the [ON CONFLICT] mode
** is for the SQL statement being evaluated.

** transaction open on the database, or if the database is not a wal mode
** database.
**
** SQLITE_OK is returned if successful, or an SQLite error code otherwise.
*/
SQLITE_EXPERIMENTAL int sqlite3_snapshot_recover(sqlite3 *db, const char *zDb);

/*
** This function is used to register a whereinfo hook with the database
** handle passed as the first argument. Once registered, the whereinfo hook
** is invoked zero or more times while preparing a query to provide
** information to the application. It is intended to be used by expert 
** systems to recommend indexes that could be added to the database in order
** to improve query response time.
**
** An SQLite query plan describes the way data is read from zero or more
** database tables. For each table read, the data required may be
** constrained by equality or range constraints on one or more columns, 
** and it may or may not be required in order sorted by one or more 
** columns. For example, the following query:
**
** <pre>
**     SELECT * FROM t1 WHERE t1.a = ? ORDER BY t1.b;
** </pre>
**
** reads data from table t1. It requires only those rows for which t1.a
** is set to a specific value, and requires them sorted in order of
** column t1.b. Internally, SQLite determines this and attempts to locate
** an index that can be used to efficiently find the required subset of
** rows and/or allows the rows to be read from the database in the 
** required order. In this case, ideally an index of the form:
**
** <pre>
**     CREATE INDEX i1 ON t1(a, b);
** </pre>
**
** The data passed to the whereinfo hook during query preparation do
** not describe the actual query plan to the application. Instead, it
** describes the parts of the query that SQLite could use an index to
** optimize if a suitable index existed. In this case, that only
** rows with t1.a=? are required, and that they are required sorted
** in order by t1.b.
**
** Each time the whereinfo hook is invoked, the first argument is a
** copy of the (void*) pointer passed as the second argument to this
** API function. The second is always one of the SQLITE_WHEREINFO_XXX
** constants defined below.
**
** For each table read by a query, the whereinfo hook is invoked as follows:
**
** <ul>
**   <li> Once with SQLITE_WHEREINFO_TABLE as the second argument. This
**        indicates the table that subsequent callbacks (until the next
**        SQLITE_WHEREINFO_TABLE) apply to.
**
**   <li> If SQLite requires rows in a specific order, once with
**        SQLITE_WHEREINFO_ORDERBY for each column of the table that is
**        one of the sort keys.
**
**   <li> If there are any "<col> = ?" constraints that restrict the rows
**        required by SQLite, once with SQLITE_WHEREINFO_EQUALS for each
**        such constraint.
**
**   <li> If there are any "<col> > ?" constraints (or any other range
**        constraint) that restrict the rows required by SQLite, once with 
**        SQLITE_WHEREINFO_RANGE for each such constraint.
** </ul>
**
** The third, fourth and fifth arguments passed to the whereinfo callback
** are interpreted differently, depending on the SQLITE_WHEREINFO_XXX value
** as follows:
**
** <dl>
**   <dt> SQLITE_WHEREINFO_TABLE
**   <dd> The third argument passed in this case is the name of the table.
**        The fourth is the index of the database in which the table is
**        located (0 for "main", 1 for "temp" or higher for an attached
**        database). The fifth argument is a bitmask that indicates which
**        of the tables columns may be required by the query. If the leftmost
**        column of the table is used in some way, bit 0 of the bitmask is
**        set. If the next-to-leftmost is used, bit 1 etc. Bit 63 is used to
**        represent all columns with an index of 63 or higher. If bit 63
**        is set, the application should assume that the query requires all
**        columns from the table with an index of 63 or greater.
**
**   <dt> SQLITE_WHEREINFO_ORDERBY
**   <dd> The third argument passed in this case is the name of the collation
**        sequence to sort by. The fourth is the index of the table column to
**        sort by (0 for the leftmost column, 1 for the next-to-leftmost
**        etc.). The fifth argument is a boolean flag - true for a DESC sort
**        or false for ASC.
**
**   <dt> SQLITE_WHEREINFO_EQUALS
**   <dd> The third argument passed in this case is the name of the collation
**        sequence used by the constraint. The fourth is the index of the 
**        table column in the constraint. If the current table is not part
**        of a join, then the value passed as the fifth argument is always
**        zero. Or, if it is part of a join, then the fifth parameter passed
**        to this callback is a mask of other tables that the current
**        constraint depends on. For example, in the query:
**
**   <pre>
**      SELECT * FROM t1, t2 WHERE t1.a = (t2.b+1);
**   </pre>
**
**        the fifth parameter passed to the the SQLITE_WHEREINFO_EQUALS
**        whereinfo callback would have the bit assigned to table "t2"
**        set to true. There is no way for the application to determine 
**        the specific bit in the mask assigned to any table, but the bit
**        assignments are consistent while parsing a single query.
**
**   <dt> SQLITE_WHEREINFO_RANGE
**   <dd> As for SQLITE_WHEREINFO_EQUALS.
** </dl>
**
** Note that if a WHERE clause includes an OR expression, then there may be
** more than one set of callbacks for a single table. For example, the
** following SQL:
**
** <pre>
**    SELECT * FROM t1 WHERE t1.a=? OR t1.b=?
** </pre>
**
** Provokes the same callbacks as the following two queries executed in
** series.
**
** <pre>
**    SELECT * FROM t1 WHERE t1.a=?;
**    SELECT * FROM t1 WHERE t1.b=?;
** </pre>
*/
SQLITE_EXPERIMENTAL void *sqlite3_whereinfo_hook(
  sqlite3 *db,                    /* Register callback with this db handle */
  void (*xWhereInfo)(
    void*,                        /* Copy of pCtx */
    int,                          /* SQLITE_WHEREINFO_XXX constant */
    const char*,
    int,
    sqlite3_uint64
  ),
  void *pCtx                      /* User pointer passed to callback */
);

#define SQLITE_WHEREINFO_TABLE   1
#define SQLITE_WHEREINFO_EQUALS  2
#define SQLITE_WHEREINFO_RANGE   3
#define SQLITE_WHEREINFO_ORDERBY 4

/*
** 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 /* SQLITE3_H */

#endif
#ifndef SQLITE_OMIT_VIRTUALTABLE
  int nVTrans;                  /* Allocated size of aVTrans */
  Hash aModule;                 /* populated by sqlite3_create_module() */
  VtabCtx *pVtabCtx;            /* Context for active vtab connect/create */
  VTable **aVTrans;             /* Virtual tables with open transactions */
  VTable *pDisconnect;    /* Disconnect these in next sqlite3_prepare() */

#endif
  Hash aFunc;                   /* Hash table of connection functions */
  Hash aCollSeq;                /* All collating sequences */
  BusyHandler busyHandler;      /* Busy callback */
  Db aDbStatic[2];              /* Static space for the 2 default backends */
  Savepoint *pSavepoint;        /* List of active savepoints */
  int busyTimeout;              /* Busy handler timeout, in msec */

  void *pUnlockArg;                     /* Argument to xUnlockNotify */
  void (*xUnlockNotify)(void **, int);  /* Unlock notify callback */
  sqlite3 *pNextBlocked;        /* Next in list of all blocked connections */
#endif
#ifdef SQLITE_USER_AUTHENTICATION
  sqlite3_userauth auth;        /* User authentication information */
#endif
#ifdef SQLITE_ENABLE_WHEREINFO_HOOK
  void (*xWhereInfo)(void*, int, const char*, int, u64);
  void *pWhereInfoCtx;
#endif
};

/*
** A macro to discover the encoding of a database.
*/
#define SCHEMA_ENC(db) ((db)->aDb[0].pSchema->enc)
#define ENC(db)        ((db)->enc)

    }
  }

  /* Allocate the sqlite3_index_info structure
  */
  pIdxInfo = sqlite3DbMallocZero(pParse->db, sizeof(*pIdxInfo)
                           + (sizeof(*pIdxCons) + sizeof(*pUsage))*nTerm
                           + sizeof(*pIdxOrderBy)*nOrderBy );

  if( pIdxInfo==0 ){
    sqlite3ErrorMsg(pParse, "out of memory");
    return 0;
  }

  /* Initialize the structure.  The sqlite3_index_info structure contains
  ** many fields that are declared "const" to prevent xBestIndex from

  WHERETRACE(0xffff, ("  bIn=%d prereqIn=%04llx prereqOut=%04llx\n",
                      *pbIn, (sqlite3_uint64)mPrereq,
                      (sqlite3_uint64)(pNew->prereq & ~mPrereq)));

  return rc;
}






























/*
** Add all WhereLoop objects for a table of the join identified by
** pBuilder->pNew->iTab.  That table is guaranteed to be a virtual table.
**
** If there are no LEFT or CROSS JOIN joins in the query, both mPrereq and
** mUnusable are set to 0. Otherwise, mPrereq is a mask of all FROM clause

  struct SrcList_item *pSrc;   /* The FROM clause term to search */
  sqlite3_index_info *p;       /* Object to pass to xBestIndex() */
  int nConstraint;             /* Number of constraints in p */
  int bIn;                     /* True if plan uses IN(...) operator */
  WhereLoop *pNew;
  Bitmask mBest;               /* Tables used by best possible plan */
  u16 mNoOmit;



  assert( (mPrereq & mUnusable)==0 );
  pWInfo = pBuilder->pWInfo;
  pParse = pWInfo->pParse;
  pWC = pBuilder->pWC;
  pNew = pBuilder->pNew;
  pSrc = &pWInfo->pTabList->a[pNew->iTab];

  pNew->u.vtab.needFree = 0;
  nConstraint = p->nConstraint;
  if( whereLoopResize(pParse->db, pNew, nConstraint) ){
    sqlite3DbFree(pParse->db, p);
    return SQLITE_NOMEM_BKPT;
  }








  /* First call xBestIndex() with all constraints usable. */
  WHERETRACE(0x40, ("  VirtualOne: all usable\n"));
  rc = whereLoopAddVirtualOne(pBuilder, mPrereq, ALLBITS, 0, p, mNoOmit, &bIn);

  /* If the call to xBestIndex() with all terms enabled produced a plan
  ** that does not require any source tables (IOW: a plan with mBest==0),
  ** then there is no point in making any further calls to xBestIndex() 

      rc = whereLoopAddVirtualOne(
          pBuilder, mPrereq, mPrereq, WO_IN, p, mNoOmit, &bIn);
    }
  }

  if( p->needToFreeIdxStr ) sqlite3_free(p->idxStr);
  sqlite3DbFreeNN(pParse->db, p);

  return rc;
}
#endif /* SQLITE_OMIT_VIRTUALTABLE */

/*
** Add WhereLoop entries to handle OR terms.  This works for either
** btrees or virtual tables.

  WhereTerm *pTerm, *pWCEnd;
  int rc = SQLITE_OK;
  int iCur;
  WhereClause tempWC;
  WhereLoopBuilder sSubBuild;
  WhereOrSet sSum, sCur;
  struct SrcList_item *pItem;

  pWC = pBuilder->pWC;
  pWCEnd = pWC->a + pWC->nTerm;
  pNew = pBuilder->pNew;
  memset(&sSum, 0, sizeof(sSum));
  pItem = pWInfo->pTabList->a + pNew->iTab;
  iCur = pItem->iCursor;

  for(pTerm=pWC->a; pTerm<pWCEnd && rc==SQLITE_OK; pTerm++){
    if( (pTerm->eOperator & WO_OR)!=0
     && (pTerm->u.pOrInfo->indexable & pNew->maskSelf)!=0 
    ){
      WhereClause * const pOrWC = &pTerm->u.pOrInfo->wc;
      WhereTerm * const pOrWCEnd = &pOrWC->a[pOrWC->nTerm];
      WhereTerm *pOrTerm;
      int once = 1;
      int i, j;

      sSubBuild = *pBuilder;
      sSubBuild.pOrderBy = 0;
      sSubBuild.pOrSet = &sCur;

      WHERETRACE(0x200, ("Begin processing OR-clause %p\n", pTerm));
      for(pOrTerm=pOrWC->a; pOrTerm<pOrWCEnd; pOrTerm++){
        if( (pOrTerm->eOperator & WO_AND)!=0 ){

    pLoop->cId = '0';
#endif
    return 1;
  }
  return 0;
}

#ifdef SQLITE_ENABLE_WHEREINFO_HOOK

static void whereTraceWC(
  Parse *pParse, 
  struct SrcList_item *pItem,
  WhereClause *pWC
){
  sqlite3 *db = pParse->db;
  Table *pTab = pItem->pTab;
  void (*x)(void*, int, const char*, int, u64) = db->xWhereInfo;
  void *pCtx = db->pWhereInfoCtx;
  int ii;

  /* Issue callbacks for WO_SINGLE constraints */
  for(ii=0; ii<pTab->nCol; ii++){
    int opMask = WO_SINGLE; 
    WhereScan scan;
    WhereTerm *pTerm;
    for(pTerm=whereScanInit(&scan, pWC, pItem->iCursor, ii, opMask, 0);
        pTerm;
        pTerm=whereScanNext(&scan)
    ){
      int eOp;
      Expr *pX = pTerm->pExpr;
      CollSeq *pC = sqlite3BinaryCompareCollSeq(pParse, pX->pLeft, pX->pRight);
      if( pTerm->eOperator & (WO_IS|WO_EQ|WO_IN) ){
        eOp = SQLITE_WHEREINFO_EQUALS;
      }else{
        eOp = SQLITE_WHEREINFO_RANGE;
      }
      x(pCtx, eOp, (pC ? pC->zName : "BINARY"), ii, pTerm->prereqRight);
    }
  }
}

/*
** If there are any OR terms in WHERE clause pWC, make the associated
** where-info hook callbacks.
*/
static void whereTraceOR(
  Parse *pParse, 
  struct SrcList_item *pItem,
  WhereClause *pWC
){
  sqlite3 *db = pParse->db;
  WhereClause tempWC;
  struct TermAndIdx {
    WhereTerm *pTerm;
    int iIdx;
  } aOr[4];
  int nOr = 0;
  Table *pTab = pItem->pTab;
  int iDb = sqlite3SchemaToIndex(db, pTab->pSchema);
  int ii;

  memset(aOr, 0, sizeof(aOr));

  /* Iterate through OR nodes */
  for(ii=0; ii<pWC->nTerm; ii++){
    WhereTerm *pTerm = &pWC->a[ii];
    if( pTerm->eOperator & WO_OR ){
      /* Check that each branch of this OR term contains at least
      ** one reference to the table currently being processed. If that
      ** is not the case, this term can be ignored.  */
      WhereClause * const pOrWC = &pTerm->u.pOrInfo->wc;
      WhereTerm * const pOrWCEnd = &pOrWC->a[pOrWC->nTerm];
      WhereTerm *pOrTerm;
      WhereClause *pTermWC;
      WhereScan scan;

      for(pOrTerm=pOrWC->a; pOrTerm<pOrWCEnd; pOrTerm++){
        int iCol;
        if( (pOrTerm->eOperator & WO_AND)!=0 ){
          pTermWC = &pOrTerm->u.pAndInfo->wc;
        }else{
          tempWC.pWInfo = pWC->pWInfo;
          tempWC.pOuter = pWC;
          tempWC.op = TK_AND;
          tempWC.nTerm = 1;
          tempWC.a = pOrTerm;
          pTermWC = &tempWC;
        }

        for(iCol=0; iCol<pTab->nCol; iCol++){
          int iCsr = pItem->iCursor;
          if( !whereScanInit(&scan, pTermWC, iCsr, iCol, WO_SINGLE, 0) ){
            break;
          }
        }
        if( iCol==pTab->nCol ) break;
      }

      if( pOrTerm==pOrWCEnd ){
        aOr[nOr].pTerm = pTerm;
        aOr[nOr].iIdx = pOrWC->nTerm;
        nOr++;
        if( nOr==ArraySize(aOr) ) break;
      }
    }
  }

  while( 1 ){
    for(ii=0; ii<nOr; ii++){
      if( aOr[ii].iIdx==0 ){
        aOr[ii].iIdx = aOr[ii].pTerm->u.pOrInfo->wc.nTerm;
      }else{
        aOr[ii].iIdx--;
        break;
      }
    }
    if( ii==nOr ) break;

    /* Table name callback */
    db->xWhereInfo(db->pWhereInfoCtx, 
        SQLITE_WHEREINFO_TABLE, pTab->zName, iDb, pItem->colUsed
    );
    /* whereTraceWC(pParse, pItem, pWC); */
    for(ii=0; ii<nOr; ii++){
      WhereClause * const pOrWC = &aOr[ii].pTerm->u.pOrInfo->wc;
      if( aOr[ii].iIdx<pOrWC->nTerm ){
        WhereClause *pTermWC;
        WhereTerm *pOrTerm = &pOrWC->a[aOr[ii].iIdx];
        if( (pOrTerm->eOperator & WO_AND)!=0 ){
          pTermWC = &pOrTerm->u.pAndInfo->wc;
        }else{
          tempWC.pWInfo = pWC->pWInfo;
          tempWC.pOuter = pWC;
          tempWC.op = TK_AND;
          tempWC.nTerm = 1;
          tempWC.a = pOrTerm;
          pTermWC = &tempWC;
        }
        whereTraceWC(pParse, pItem, pTermWC);
      }
    }
  }
}

/*
** If there is a where-info hook attached to the database handle, issue all
** required callbacks for the current sqlite3WhereBegin() call.
*/
static void whereTraceBuilder(
  Parse *pParse,
  WhereLoopBuilder *p
){
  sqlite3 *db = pParse->db;
  if( db->xWhereInfo && db->init.busy==0 ){
    void (*x)(void*, int, const char*, int, u64) = db->xWhereInfo;
    void *pCtx = db->pWhereInfoCtx;
    int ii;
    SrcList *pTabList = p->pWInfo->pTabList;

    /* Loop through each element of the FROM clause. Ignore any sub-selects
    ** or views. Invoke the xWhereInfo() callback multiple times for each
    ** real table.  */
    for(ii=0; ii<pTabList->nSrc; ii++){
      struct SrcList_item *pItem = &pTabList->a[ii];
      if( pItem->pSelect==0 ){
        Table *pTab = pItem->pTab;
        int iDb = sqlite3SchemaToIndex(db, pTab->pSchema);

        /* Table name callback */
        x(pCtx, SQLITE_WHEREINFO_TABLE, pTab->zName, iDb, pItem->colUsed);

        /* ORDER BY callbacks */
        if( p->pOrderBy ){
          int i;
          for(i=0; i<p->pOrderBy->nExpr; i++){
            Expr *pExpr = p->pOrderBy->a[i].pExpr; 
            CollSeq *pColl = sqlite3ExprCollSeq(pParse, pExpr);
            pExpr = sqlite3ExprSkipCollate(pExpr);
            if( pExpr->op==TK_COLUMN && pExpr->iTable==pItem->iCursor ){
              int iCol = pExpr->iColumn;
              if( pColl && iCol>=0 ){
                int bDesc = p->pOrderBy->a[i].sortOrder;
                x(pCtx, SQLITE_WHEREINFO_ORDERBY, pColl->zName, iCol, bDesc); 
              }
            }
          }
        }

        /* WHERE callbacks */
        whereTraceWC(pParse, pItem, p->pWC);

        /* OR-clause processing */
        whereTraceOR(pParse, pItem, p->pWC);
      }
    }
  }
}
#else
# define whereTraceBuilder(x,y)
#endif

/*
** 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.
**

    sqlite3DebugPrintf(")\n");
  }
  if( sqlite3WhereTrace & 0x100 ){ /* Display all terms of the WHERE clause */
    sqlite3WhereClausePrint(sWLB.pWC);
  }
#endif

  /* Invoke the where-info hook, if one has been registered. */
  whereTraceBuilder(pParse, &sWLB);

  if( nTabList!=1 || whereShortCut(&sWLB)==0 ){
    rc = whereLoopAddAll(&sWLB);
    if( rc ) goto whereBeginError;
  
#ifdef WHERETRACE_ENABLED
    if( sqlite3WhereTrace ){    /* Display all of the WhereLoop objects */
      WhereLoop *p;