Fossil

** in bytes.  This is different from the %*.*s specification in printf
** since with %*.*s the width is measured in bytes, not characters.
*/
static void utf8_width_print(FILE *pOut, int w, const char *zUtf){
  int i;
  int n;
  int aw = w<0 ? -w : w;
  if( zUtf==0 ) zUtf = "";
  for(i=n=0; zUtf[i]; i++){
    if( (zUtf[i]&0xc0)!=0x80 ){
      n++;
      if( n==aw ){
        do{ i++; }while( (zUtf[i]&0xc0)==0x80 );
        break;
      }

}

#endif /* ifndef SQLITE_OMIT_VIRTUALTABLE */

/************************* End ../ext/expert/sqlite3expert.c ********************/

#if !defined(SQLITE_OMIT_VIRTUALTABLE) && defined(SQLITE_ENABLE_DBPAGE_VTAB)
#define SQLITE_SHELL_HAVE_RECOVER 1
#else
#define SQLITE_SHELL_HAVE_RECOVER 0
#endif
#if SQLITE_SHELL_HAVE_RECOVER
/************************* Begin ../ext/recover/dbdata.c ******************/
/*
** 2019-04-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.

**       child INTEGER,
**       schema TEXT HIDDEN
**     );
**
**   It contains one entry for each b-tree pointer between a parent and
**   child page in the database.
*/

#if !defined(SQLITEINT_H) 
/* #include "sqlite3ext.h" */

/* typedef unsigned char u8; */
typedef unsigned int u32;

#endif
SQLITE_EXTENSION_INIT1
#include <string.h>
#include <assert.h>

#ifndef SQLITE_OMIT_VIRTUALTABLE

#define DBDATA_PADDING_BYTES 100 

typedef struct DbdataTable DbdataTable;
typedef struct DbdataCursor DbdataCursor;

/* Cursor object */

  int iCell;                      /* Current cell number */
  int bOnePage;                   /* True to stop after one page */
  int szDb;
  sqlite3_int64 iRowid;

  /* Only for the sqlite_dbdata table */
  u8 *pRec;                       /* Buffer containing current record */
  sqlite3_int64 nRec;             /* Size of pRec[] in bytes */
  sqlite3_int64 nHdr;             /* Size of header in bytes */
  int iField;                     /* Current field number */
  u8 *pHdrPtr;
  u8 *pPtr;
  u32 enc;                        /* Text encoding */
  
  sqlite3_int64 iIntkey;          /* Integer key value */
};

/* Table object */
struct DbdataTable {
  sqlite3_vtab base;              /* Base class.  Must be first */

  sqlite3_free(pCsr);
  return SQLITE_OK;
}

/* 
** Utility methods to decode 16 and 32-bit big-endian unsigned integers. 
*/
static u32 get_uint16(unsigned char *a){
  return (a[0]<<8)|a[1];
}
static u32 get_uint32(unsigned char *a){
  return ((u32)a[0]<<24)
       | ((u32)a[1]<<16)
       | ((u32)a[2]<<8)
       | ((u32)a[3]);
}

/*
** Load page pgno from the database via the sqlite_dbpage virtual table.
** If successful, set (*ppPage) to point to a buffer containing the page
** data, (*pnPage) to the size of that buffer in bytes and return
** SQLITE_OK. In this case it is the responsibility of the caller to
** eventually free the buffer using sqlite3_free().
**
** Or, if an error occurs, set both (*ppPage) and (*pnPage) to 0 and
** return an SQLite error code.
*/
static int dbdataLoadPage(
  DbdataCursor *pCsr,             /* Cursor object */
  u32 pgno,                       /* Page number of page to load */
  u8 **ppPage,                    /* OUT: pointer to page buffer */
  int *pnPage                     /* OUT: Size of (*ppPage) in bytes */
){
  int rc2;
  int rc = SQLITE_OK;
  sqlite3_stmt *pStmt = pCsr->pStmt;

  *ppPage = 0;
  *pnPage = 0;
  if( pgno>0 ){
    sqlite3_bind_int64(pStmt, 2, pgno);
    if( SQLITE_ROW==sqlite3_step(pStmt) ){
      int nCopy = sqlite3_column_bytes(pStmt, 0);
      if( nCopy>0 ){
        u8 *pPage;
        pPage = (u8*)sqlite3_malloc64(nCopy + DBDATA_PADDING_BYTES);
        if( pPage==0 ){
          rc = SQLITE_NOMEM;
        }else{
          const u8 *pCopy = sqlite3_column_blob(pStmt, 0);
          memcpy(pPage, pCopy, nCopy);
          memset(&pPage[nCopy], 0, DBDATA_PADDING_BYTES);
        }
        *ppPage = pPage;
        *pnPage = nCopy;
      }
    }
    rc2 = sqlite3_reset(pStmt);
    if( rc==SQLITE_OK ) rc = rc2;
  }

  return rc;
}

/*
** Read a varint.  Put the value in *pVal and return the number of bytes.
*/
static int dbdataGetVarint(const u8 *z, sqlite3_int64 *pVal){
  sqlite3_uint64 u = 0;
  int i;
  for(i=0; i<8; i++){
    u = (u<<7) + (z[i]&0x7f);
    if( (z[i]&0x80)==0 ){ *pVal = (sqlite3_int64)u; return i+1; }
  }
  u = (u<<8) + (z[i]&0xff);
  *pVal = (sqlite3_int64)u;
  return 9;
}

/*
** Like dbdataGetVarint(), but set the output to 0 if it is less than 0
** or greater than 0xFFFFFFFF. This can be used for all varints in an
** SQLite database except for key values in intkey tables.
*/
static int dbdataGetVarintU32(const u8 *z, sqlite3_int64 *pVal){
  sqlite3_int64 val;
  int nRet = dbdataGetVarint(z, &val);
  if( val<0 || val>0xFFFFFFFF ) val = 0;
  *pVal = val;
  return nRet;
}

/*
** Return the number of bytes of space used by an SQLite value of type
** eType.
*/
static int dbdataValueBytes(int eType){
  switch( eType ){

/*
** Load a value of type eType from buffer pData and use it to set the
** result of context object pCtx.
*/
static void dbdataValue(
  sqlite3_context *pCtx, 
  u32 enc,
  int eType, 
  u8 *pData,
  int nData
){
  if( eType>=0 && dbdataValueBytes(eType)<=nData ){
    switch( eType ){
      case 0: 

        }
        break;
      }
  
      default: {
        int n = ((eType-12) / 2);
        if( eType % 2 ){
          switch( enc ){
#ifndef SQLITE_OMIT_UTF16
            case SQLITE_UTF16BE:
              sqlite3_result_text16be(pCtx, (void*)pData, n, SQLITE_TRANSIENT);
              break;
            case SQLITE_UTF16LE:
              sqlite3_result_text16le(pCtx, (void*)pData, n, SQLITE_TRANSIENT);
              break;
#endif
            default:
              sqlite3_result_text(pCtx, (char*)pData, n, SQLITE_TRANSIENT);
              break;
          }
        }else{
          sqlite3_result_blob(pCtx, pData, n, SQLITE_TRANSIENT);
        }
      }
    }
  }
}

    if( pCsr->aPage==0 ){
      while( 1 ){
        if( pCsr->bOnePage==0 && pCsr->iPgno>pCsr->szDb ) return SQLITE_OK;
        rc = dbdataLoadPage(pCsr, pCsr->iPgno, &pCsr->aPage, &pCsr->nPage);
        if( rc!=SQLITE_OK ) return rc;
        if( pCsr->aPage ) break;
        if( pCsr->bOnePage ) return SQLITE_OK;
        pCsr->iPgno++;
      }
      pCsr->iCell = pTab->bPtr ? -2 : 0;
      pCsr->nCell = get_uint16(&pCsr->aPage[iOff+3]);
    }

    if( pTab->bPtr ){

          /* For an interior node cell, skip past the child-page number */
          iOff += nPointer;
    
          /* Load the "byte of payload including overflow" field */
          if( bNextPage || iOff>pCsr->nPage ){
            bNextPage = 1;
          }else{
            iOff += dbdataGetVarintU32(&pCsr->aPage[iOff], &nPayload);
          }
    
          /* If this is a leaf intkey cell, load the rowid */
          if( bHasRowid && !bNextPage && iOff<pCsr->nPage ){
            iOff += dbdataGetVarint(&pCsr->aPage[iOff], &pCsr->iIntkey);
          }
    

            /* Load the nLocal bytes of payload */
            memcpy(pCsr->pRec, &pCsr->aPage[iOff], nLocal);
            iOff += nLocal;

            /* Load content from overflow pages */
            if( nPayload>nLocal ){
              sqlite3_int64 nRem = nPayload - nLocal;
              u32 pgnoOvfl = get_uint32(&pCsr->aPage[iOff]);
              while( nRem>0 ){
                u8 *aOvfl = 0;
                int nOvfl = 0;
                int nCopy;
                rc = dbdataLoadPage(pCsr, pgnoOvfl, &aOvfl, &nOvfl);
                assert( rc!=SQLITE_OK || aOvfl==0 || nOvfl==pCsr->nPage );
                if( rc!=SQLITE_OK ) return rc;
                if( aOvfl==0 ) break;

                nCopy = U-4;
                if( nCopy>nRem ) nCopy = nRem;
                memcpy(&pCsr->pRec[nPayload-nRem], &aOvfl[4], nCopy);
                nRem -= nCopy;

                pgnoOvfl = get_uint32(aOvfl);
                sqlite3_free(aOvfl);
              }
            }
    
            iHdr = dbdataGetVarintU32(pCsr->pRec, &nHdr);
            if( nHdr>nPayload ) nHdr = 0;
            pCsr->nHdr = nHdr;
            pCsr->pHdrPtr = &pCsr->pRec[iHdr];
            pCsr->pPtr = &pCsr->pRec[pCsr->nHdr];
            pCsr->iField = (bHasRowid ? -1 : 0);
          }
        }
      }else{
        pCsr->iField++;
        if( pCsr->iField>0 ){
          sqlite3_int64 iType;
          if( pCsr->pHdrPtr>&pCsr->pRec[pCsr->nRec] ){
            bNextPage = 1;
          }else{
            pCsr->pHdrPtr += dbdataGetVarintU32(pCsr->pHdrPtr, &iType);
            pCsr->pPtr += dbdataValueBytes(iType);
          }
        }
      }

      if( bNextPage ){
        sqlite3_free(pCsr->aPage);

/* 
** Return true if the cursor is at EOF.
*/
static int dbdataEof(sqlite3_vtab_cursor *pCursor){
  DbdataCursor *pCsr = (DbdataCursor*)pCursor;
  return pCsr->aPage==0;
}

/*
** Return true if nul-terminated string zSchema ends in "()". Or false
** otherwise.
*/
static int dbdataIsFunction(const char *zSchema){
  size_t n = strlen(zSchema);
  if( n>2 && zSchema[n-2]=='(' && zSchema[n-1]==')' ){
    return (int)n-2;
  }
  return 0;
}

/* 
** Determine the size in pages of database zSchema (where zSchema is
** "main", "temp" or the name of an attached database) and set 
** pCsr->szDb accordingly. If successful, return SQLITE_OK. Otherwise,
** an SQLite error code.
*/
static int dbdataDbsize(DbdataCursor *pCsr, const char *zSchema){
  DbdataTable *pTab = (DbdataTable*)pCsr->base.pVtab;
  char *zSql = 0;
  int rc, rc2;
  int nFunc = 0;
  sqlite3_stmt *pStmt = 0;

  if( (nFunc = dbdataIsFunction(zSchema))>0 ){
    zSql = sqlite3_mprintf("SELECT %.*s(0)", nFunc, zSchema);
  }else{
    zSql = sqlite3_mprintf("PRAGMA %Q.page_count", zSchema);
  }
  if( zSql==0 ) return SQLITE_NOMEM;

  rc = sqlite3_prepare_v2(pTab->db, zSql, -1, &pStmt, 0);
  sqlite3_free(zSql);
  if( rc==SQLITE_OK && sqlite3_step(pStmt)==SQLITE_ROW ){
    pCsr->szDb = sqlite3_column_int(pStmt, 0);
  }
  rc2 = sqlite3_finalize(pStmt);
  if( rc==SQLITE_OK ) rc = rc2;
  return rc;
}

/*
** Attempt to figure out the encoding of the database by retrieving page 1
** and inspecting the header field. If successful, set the pCsr->enc variable
** and return SQLITE_OK. Otherwise, return an SQLite error code.
*/
static int dbdataGetEncoding(DbdataCursor *pCsr){
  int rc = SQLITE_OK;
  int nPg1 = 0;
  u8 *aPg1 = 0;
  rc = dbdataLoadPage(pCsr, 1, &aPg1, &nPg1);
  assert( rc!=SQLITE_OK || nPg1==0 || nPg1>=512 );
  if( rc==SQLITE_OK && nPg1>0 ){
    pCsr->enc = get_uint32(&aPg1[56]);
  }
  sqlite3_free(aPg1);
  return rc;
}


/* 
** xFilter method for sqlite_dbdata and sqlite_dbptr.
*/
static int dbdataFilter(
  sqlite3_vtab_cursor *pCursor, 
  int idxNum, const char *idxStr,
  int argc, sqlite3_value **argv
){
  DbdataCursor *pCsr = (DbdataCursor*)pCursor;
  DbdataTable *pTab = (DbdataTable*)pCursor->pVtab;
  int rc = SQLITE_OK;
  const char *zSchema = "main";

  dbdataResetCursor(pCsr);
  assert( pCsr->iPgno==1 );
  if( idxNum & 0x01 ){
    zSchema = (const char*)sqlite3_value_text(argv[0]);
    if( zSchema==0 ) zSchema = "";
  }
  if( idxNum & 0x02 ){
    pCsr->iPgno = sqlite3_value_int(argv[(idxNum & 0x01)]);
    pCsr->bOnePage = 1;
  }else{

    rc = dbdataDbsize(pCsr, zSchema);
  }

  if( rc==SQLITE_OK ){
    int nFunc = 0;
    if( pTab->pStmt ){
      pCsr->pStmt = pTab->pStmt;
      pTab->pStmt = 0;
    }else if( (nFunc = dbdataIsFunction(zSchema))>0 ){
      char *zSql = sqlite3_mprintf("SELECT %.*s(?2)", nFunc, zSchema);
      if( zSql==0 ){
        rc = SQLITE_NOMEM;
      }else{
        rc = sqlite3_prepare_v2(pTab->db, zSql, -1, &pCsr->pStmt, 0);
        sqlite3_free(zSql);
      }
    }else{
      rc = sqlite3_prepare_v2(pTab->db, 
          "SELECT data FROM sqlite_dbpage(?) WHERE pgno=?", -1,
          &pCsr->pStmt, 0
      );
    }
  }
  if( rc==SQLITE_OK ){
    rc = sqlite3_bind_text(pCsr->pStmt, 1, zSchema, -1, SQLITE_TRANSIENT);
  }else{
    pTab->base.zErrMsg = sqlite3_mprintf("%s", sqlite3_errmsg(pTab->db));
  }

  /* Try to determine the encoding of the db by inspecting the header
  ** field on page 1. */
  if( rc==SQLITE_OK ){
    rc = dbdataGetEncoding(pCsr);
  }

  if( rc==SQLITE_OK ){
    rc = dbdataNext(pCursor);
  }
  return rc;
}

/*
** Return a column for the sqlite_dbdata or sqlite_dbptr table.
*/
static int dbdataColumn(
  sqlite3_vtab_cursor *pCursor, 
  sqlite3_context *ctx, 
  int i
){

        sqlite3_result_int(ctx, pCsr->iField);
        break;
      case DBDATA_COLUMN_VALUE: {
        if( pCsr->iField<0 ){
          sqlite3_result_int64(ctx, pCsr->iIntkey);
        }else{
          sqlite3_int64 iType;
          dbdataGetVarintU32(pCsr->pHdrPtr, &iType);
          dbdataValue(
              ctx, pCsr->enc, iType, pCsr->pPtr, 
              &pCsr->pRec[pCsr->nRec] - pCsr->pPtr
          );
        }
        break;
      }
    }
  }
  return SQLITE_OK;

  char **pzErrMsg, 
  const sqlite3_api_routines *pApi
){
  SQLITE_EXTENSION_INIT2(pApi);
  return sqlite3DbdataRegister(db);
}

#endif /* ifndef SQLITE_OMIT_VIRTUALTABLE */

/************************* End ../ext/recover/dbdata.c ********************/
/************************* Begin ../ext/recover/sqlite3recover.h ******************/
/*
** 2022-08-27
**
** 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 contains the public interface to the "recover" extension -
** an SQLite extension designed to recover data from corrupted database
** files.
*/

/*
** OVERVIEW:
**
** To use the API to recover data from a corrupted database, an
** application:
**
**   1) Creates an sqlite3_recover handle by calling either
**      sqlite3_recover_init() or sqlite3_recover_init_sql().
**
**   2) Configures the new handle using one or more calls to
**      sqlite3_recover_config().
**
**   3) Executes the recovery by repeatedly calling sqlite3_recover_step() on
**      the handle until it returns something other than SQLITE_OK. If it
**      returns SQLITE_DONE, then the recovery operation completed without 
**      error. If it returns some other non-SQLITE_OK value, then an error 
**      has occurred.
**
**   4) Retrieves any error code and English language error message using the
**      sqlite3_recover_errcode() and sqlite3_recover_errmsg() APIs,
**      respectively.
**
**   5) Destroys the sqlite3_recover handle and frees all resources
**      using sqlite3_recover_finish().
**
** The application may abandon the recovery operation at any point 
** before it is finished by passing the sqlite3_recover handle to
** sqlite3_recover_finish(). This is not an error, but the final state
** of the output database, or the results of running the partial script
** delivered to the SQL callback, are undefined.
*/

#ifndef _SQLITE_RECOVER_H
#define _SQLITE_RECOVER_H

/* #include "sqlite3.h" */

#ifdef __cplusplus
extern "C" {
#endif

/*
** An instance of the sqlite3_recover object represents a recovery
** operation in progress.
**
** Constructors:
**
**    sqlite3_recover_init()
**    sqlite3_recover_init_sql()
**
** Destructor:
**
**    sqlite3_recover_finish()
**
** Methods:
**
**    sqlite3_recover_config()
**    sqlite3_recover_errcode()
**    sqlite3_recover_errmsg()
**    sqlite3_recover_run()
**    sqlite3_recover_step()
*/
typedef struct sqlite3_recover sqlite3_recover;

/* 
** These two APIs attempt to create and return a new sqlite3_recover object.
** In both cases the first two arguments identify the (possibly
** corrupt) database to recover data from. The first argument is an open
** database handle and the second the name of a database attached to that
** handle (i.e. "main", "temp" or the name of an attached database).
**
** If sqlite3_recover_init() is used to create the new sqlite3_recover
** handle, then data is recovered into a new database, identified by
** string parameter zUri. zUri may be an absolute or relative file path,
** or may be an SQLite URI. If the identified database file already exists,
** it is overwritten.
**
** If sqlite3_recover_init_sql() is invoked, then any recovered data will
** be returned to the user as a series of SQL statements. Executing these
** SQL statements results in the same database as would have been created
** had sqlite3_recover_init() been used. For each SQL statement in the
** output, the callback function passed as the third argument (xSql) is 
** invoked once. The first parameter is a passed a copy of the fourth argument
** to this function (pCtx) as its first parameter, and a pointer to a
** nul-terminated buffer containing the SQL statement formated as UTF-8 as 
** the second. If the xSql callback returns any value other than SQLITE_OK,
** then processing is immediately abandoned and the value returned used as
** the recover handle error code (see below).
**
** If an out-of-memory error occurs, NULL may be returned instead of
** a valid handle. In all other cases, it is the responsibility of the
** application to avoid resource leaks by ensuring that
** sqlite3_recover_finish() is called on all allocated handles.
*/
sqlite3_recover *sqlite3_recover_init(
  sqlite3* db, 
  const char *zDb, 
  const char *zUri
);
sqlite3_recover *sqlite3_recover_init_sql(
  sqlite3* db, 
  const char *zDb, 
  int (*xSql)(void*, const char*),
  void *pCtx
);

/*
** Configure an sqlite3_recover object that has just been created using
** sqlite3_recover_init() or sqlite3_recover_init_sql(). This function
** may only be called before the first call to sqlite3_recover_step()
** or sqlite3_recover_run() on the object.
**
** The second argument passed to this function must be one of the
** SQLITE_RECOVER_* symbols defined below. Valid values for the third argument
** depend on the specific SQLITE_RECOVER_* symbol in use.
**
** SQLITE_OK is returned if the configuration operation was successful,
** or an SQLite error code otherwise.
*/
int sqlite3_recover_config(sqlite3_recover*, int op, void *pArg);

/*
** SQLITE_RECOVER_LOST_AND_FOUND:
**   The pArg argument points to a string buffer containing the name
**   of a "lost-and-found" table in the output database, or NULL. If
**   the argument is non-NULL and the database contains seemingly
**   valid pages that cannot be associated with any table in the
**   recovered part of the schema, data is extracted from these
**   pages to add to the lost-and-found table.
**
** SQLITE_RECOVER_FREELIST_CORRUPT:
**   The pArg value must actually be a pointer to a value of type
**   int containing value 0 or 1 cast as a (void*). If this option is set
**   (argument is 1) and a lost-and-found table has been configured using
**   SQLITE_RECOVER_LOST_AND_FOUND, then is assumed that the freelist is 
**   corrupt and an attempt is made to recover records from pages that
**   appear to be linked into the freelist. Otherwise, pages on the freelist
**   are ignored. Setting this option can recover more data from the
**   database, but often ends up "recovering" deleted records. The default 
**   value is 0 (clear).
**
** SQLITE_RECOVER_ROWIDS:
**   The pArg value must actually be a pointer to a value of type
**   int containing value 0 or 1 cast as a (void*). If this option is set
**   (argument is 1), then an attempt is made to recover rowid values
**   that are not also INTEGER PRIMARY KEY values. If this option is
**   clear, then new rowids are assigned to all recovered rows. The
**   default value is 1 (set).
**
** SQLITE_RECOVER_SLOWINDEXES:
**   The pArg value must actually be a pointer to a value of type
**   int containing value 0 or 1 cast as a (void*). If this option is clear
**   (argument is 0), then when creating an output database, the recover 
**   module creates and populates non-UNIQUE indexes right at the end of the
**   recovery operation - after all recoverable data has been inserted
**   into the new database. This is faster overall, but means that the
**   final call to sqlite3_recover_step() for a recovery operation may
**   be need to create a large number of indexes, which may be very slow.
**
**   Or, if this option is set (argument is 1), then non-UNIQUE indexes
**   are created in the output database before it is populated with 
**   recovered data. This is slower overall, but avoids the slow call
**   to sqlite3_recover_step() at the end of the recovery operation.
**
**   The default option value is 0.
*/
#define SQLITE_RECOVER_LOST_AND_FOUND   1
#define SQLITE_RECOVER_FREELIST_CORRUPT 2
#define SQLITE_RECOVER_ROWIDS           3
#define SQLITE_RECOVER_SLOWINDEXES      4

/*
** Perform a unit of work towards the recovery operation. This function 
** must normally be called multiple times to complete database recovery.
**
** If no error occurs but the recovery operation is not completed, this
** function returns SQLITE_OK. If recovery has been completed successfully
** then SQLITE_DONE is returned. If an error has occurred, then an SQLite
** error code (e.g. SQLITE_IOERR or SQLITE_NOMEM) is returned. It is not
** considered an error if some or all of the data cannot be recovered
** due to database corruption.
**
** Once sqlite3_recover_step() has returned a value other than SQLITE_OK,
** all further such calls on the same recover handle are no-ops that return
** the same non-SQLITE_OK value.
*/
int sqlite3_recover_step(sqlite3_recover*);

/* 
** Run the recovery operation to completion. Return SQLITE_OK if successful,
** or an SQLite error code otherwise. Calling this function is the same
** as executing:
**
**     while( SQLITE_OK==sqlite3_recover_step(p) );
**     return sqlite3_recover_errcode(p);
*/
int sqlite3_recover_run(sqlite3_recover*);

/*
** If an error has been encountered during a prior call to
** sqlite3_recover_step(), then this function attempts to return a 
** pointer to a buffer containing an English language explanation of 
** the error. If no error message is available, or if an out-of memory 
** error occurs while attempting to allocate a buffer in which to format
** the error message, NULL is returned.
**
** The returned buffer remains valid until the sqlite3_recover handle is
** destroyed using sqlite3_recover_finish().
*/
const char *sqlite3_recover_errmsg(sqlite3_recover*);

/*
** If this function is called on an sqlite3_recover handle after
** an error occurs, an SQLite error code is returned. Otherwise, SQLITE_OK.
*/
int sqlite3_recover_errcode(sqlite3_recover*);

/* 
** Clean up a recovery object created by a call to sqlite3_recover_init().
** The results of using a recovery object with any API after it has been
** passed to this function are undefined.
**
** This function returns the same value as sqlite3_recover_errcode().
*/
int sqlite3_recover_finish(sqlite3_recover*);


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

#endif /* ifndef _SQLITE_RECOVER_H */

/************************* End ../ext/recover/sqlite3recover.h ********************/
/************************* Begin ../ext/recover/sqlite3recover.c ******************/
/*
** 2022-08-27
**
** 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.
**
*************************************************************************
**
*/


/* #include "sqlite3recover.h" */
#include <assert.h>
#include <string.h>

#ifndef SQLITE_OMIT_VIRTUALTABLE

/*
** Declaration for public API function in file dbdata.c. This may be called
** with NULL as the final two arguments to register the sqlite_dbptr and
** sqlite_dbdata virtual tables with a database handle.
*/
#ifdef _WIN32

#endif
int sqlite3_dbdata_init(sqlite3*, char**, const sqlite3_api_routines*);

/* typedef unsigned int u32; */
/* typedef unsigned char u8; */
/* typedef sqlite3_int64 i64; */

typedef struct RecoverTable RecoverTable;
typedef struct RecoverColumn RecoverColumn;

/*
** When recovering rows of data that can be associated with table
** definitions recovered from the sqlite_schema table, each table is
** represented by an instance of the following object.
**
** iRoot:
**   The root page in the original database. Not necessarily (and usually
**   not) the same in the recovered database.
**
** zTab:
**   Name of the table.
**
** nCol/aCol[]:
**   aCol[] is an array of nCol columns. In the order in which they appear 
**   in the table.
**
** bIntkey:
**   Set to true for intkey tables, false for WITHOUT ROWID.
**
** iRowidBind:
**   Each column in the aCol[] array has associated with it the index of
**   the bind parameter its values will be bound to in the INSERT statement
**   used to construct the output database. If the table does has a rowid
**   but not an INTEGER PRIMARY KEY column, then iRowidBind contains the
**   index of the bind paramater to which the rowid value should be bound.
**   Otherwise, it contains -1. If the table does contain an INTEGER PRIMARY 
**   KEY column, then the rowid value should be bound to the index associated
**   with the column.
**
** pNext:
**   All RecoverTable objects used by the recovery operation are allocated
**   and populated as part of creating the recovered database schema in
**   the output database, before any non-schema data are recovered. They
**   are then stored in a singly-linked list linked by this variable beginning
**   at sqlite3_recover.pTblList.
*/
struct RecoverTable {
  u32 iRoot;                      /* Root page in original database */
  char *zTab;                     /* Name of table */
  int nCol;                       /* Number of columns in table */
  RecoverColumn *aCol;            /* Array of columns */
  int bIntkey;                    /* True for intkey, false for without rowid */
  int iRowidBind;                 /* If >0, bind rowid to INSERT here */
  RecoverTable *pNext;
};

/*
** Each database column is represented by an instance of the following object
** stored in the RecoverTable.aCol[] array of the associated table.
**
** iField:
**   The index of the associated field within database records. Or -1 if
**   there is no associated field (e.g. for virtual generated columns).
**
** iBind:
**   The bind index of the INSERT statement to bind this columns values
**   to. Or 0 if there is no such index (iff (iField<0)).
**
** bIPK:
**   True if this is the INTEGER PRIMARY KEY column.
**
** zCol:
**   Name of column.
**
** eHidden:
**   A RECOVER_EHIDDEN_* constant value (see below for interpretation of each).
*/
struct RecoverColumn {
  int iField;                     /* Field in record on disk */
  int iBind;                      /* Binding to use in INSERT */
  int bIPK;                       /* True for IPK column */
  char *zCol;
  int eHidden;
};

#define RECOVER_EHIDDEN_NONE    0      /* Normal database column */
#define RECOVER_EHIDDEN_HIDDEN  1      /* Column is __HIDDEN__ */
#define RECOVER_EHIDDEN_VIRTUAL 2      /* Virtual generated column */
#define RECOVER_EHIDDEN_STORED  3      /* Stored generated column */

/*
** Bitmap object used to track pages in the input database. Allocated
** and manipulated only by the following functions:
**
**     recoverBitmapAlloc()
**     recoverBitmapFree()
**     recoverBitmapSet()
**     recoverBitmapQuery()
**
** nPg:
**   Largest page number that may be stored in the bitmap. The range
**   of valid keys is 1 to nPg, inclusive.
**
** aElem[]:
**   Array large enough to contain a bit for each key. For key value
**   iKey, the associated bit is the bit (iKey%32) of aElem[iKey/32].
**   In other words, the following is true if bit iKey is set, or 
**   false if it is clear:
**
**       (aElem[iKey/32] & (1 << (iKey%32))) ? 1 : 0
*/
typedef struct RecoverBitmap RecoverBitmap;
struct RecoverBitmap {
  i64 nPg;                        /* Size of bitmap */
  u32 aElem[1];                   /* Array of 32-bit bitmasks */
};

/*
** State variables (part of the sqlite3_recover structure) used while
** recovering data for tables identified in the recovered schema (state
** RECOVER_STATE_WRITING).
*/
typedef struct RecoverStateW1 RecoverStateW1;
struct RecoverStateW1 {
  sqlite3_stmt *pTbls;
  sqlite3_stmt *pSel;
  sqlite3_stmt *pInsert;
  int nInsert;

  RecoverTable *pTab;             /* Table currently being written */
  int nMax;                       /* Max column count in any schema table */
  sqlite3_value **apVal;          /* Array of nMax values */
  int nVal;                       /* Number of valid entries in apVal[] */
  int bHaveRowid;
  i64 iRowid;
  i64 iPrevPage;
  int iPrevCell;
};

/*
** State variables (part of the sqlite3_recover structure) used while
** recovering data destined for the lost and found table (states
** RECOVER_STATE_LOSTANDFOUND[123]).
*/
typedef struct RecoverStateLAF RecoverStateLAF;
struct RecoverStateLAF {
  RecoverBitmap *pUsed;
  i64 nPg;                        /* Size of db in pages */
  sqlite3_stmt *pAllAndParent;
  sqlite3_stmt *pMapInsert;
  sqlite3_stmt *pMaxField;
  sqlite3_stmt *pUsedPages;
  sqlite3_stmt *pFindRoot;
  sqlite3_stmt *pInsert;          /* INSERT INTO lost_and_found ... */
  sqlite3_stmt *pAllPage;
  sqlite3_stmt *pPageData;
  sqlite3_value **apVal;
  int nMaxField;
};

/*
** Main recover handle structure.
*/
struct sqlite3_recover {
  /* Copies of sqlite3_recover_init[_sql]() parameters */
  sqlite3 *dbIn;                  /* Input database */
  char *zDb;                      /* Name of input db ("main" etc.) */
  char *zUri;                     /* URI for output database */
  void *pSqlCtx;                  /* SQL callback context */
  int (*xSql)(void*,const char*); /* Pointer to SQL callback function */

  /* Values configured by sqlite3_recover_config() */
  char *zStateDb;                 /* State database to use (or NULL) */
  char *zLostAndFound;            /* Name of lost-and-found table (or NULL) */
  int bFreelistCorrupt;           /* SQLITE_RECOVER_FREELIST_CORRUPT setting */
  int bRecoverRowid;              /* SQLITE_RECOVER_ROWIDS setting */
  int bSlowIndexes;               /* SQLITE_RECOVER_SLOWINDEXES setting */

  int pgsz;
  int detected_pgsz;
  int nReserve;
  u8 *pPage1Disk;
  u8 *pPage1Cache;

  /* Error code and error message */
  int errCode;                    /* For sqlite3_recover_errcode() */
  char *zErrMsg;                  /* For sqlite3_recover_errmsg() */

  int eState;
  int bCloseTransaction;

  /* Variables used with eState==RECOVER_STATE_WRITING */
  RecoverStateW1 w1;

  /* Variables used with states RECOVER_STATE_LOSTANDFOUND[123] */
  RecoverStateLAF laf;

  /* Fields used within sqlite3_recover_run() */
  sqlite3 *dbOut;                 /* Output database */
  sqlite3_stmt *pGetPage;         /* SELECT against input db sqlite_dbdata */
  RecoverTable *pTblList;         /* List of tables recovered from schema */
};

/*
** The various states in which an sqlite3_recover object may exist:
**
**   RECOVER_STATE_INIT:
**    The object is initially created in this state. sqlite3_recover_step()
**    has yet to be called. This is the only state in which it is permitted
**    to call sqlite3_recover_config().
**
**   RECOVER_STATE_WRITING:
**
**   RECOVER_STATE_LOSTANDFOUND1:
**    State to populate the bitmap of pages used by other tables or the
**    database freelist.
**
**   RECOVER_STATE_LOSTANDFOUND2:
**    Populate the recovery.map table - used to figure out a "root" page
**    for each lost page from in the database from which records are
**    extracted.
**
**   RECOVER_STATE_LOSTANDFOUND3:
**    Populate the lost-and-found table itself.
*/
#define RECOVER_STATE_INIT           0
#define RECOVER_STATE_WRITING        1
#define RECOVER_STATE_LOSTANDFOUND1  2
#define RECOVER_STATE_LOSTANDFOUND2  3
#define RECOVER_STATE_LOSTANDFOUND3  4
#define RECOVER_STATE_SCHEMA2        5
#define RECOVER_STATE_DONE           6


/*
** Global variables used by this extension.
*/
typedef struct RecoverGlobal RecoverGlobal;
struct RecoverGlobal {
  const sqlite3_io_methods *pMethods;
  sqlite3_recover *p;
};
static RecoverGlobal recover_g;

/*
** Use this static SQLite mutex to protect the globals during the
** first call to sqlite3_recover_step().
*/ 
#define RECOVER_MUTEX_ID SQLITE_MUTEX_STATIC_APP2


/* 
** Default value for SQLITE_RECOVER_ROWIDS (sqlite3_recover.bRecoverRowid).
*/
#define RECOVER_ROWID_DEFAULT 1

#if defined(SQLITE_THREADSAFE) && SQLITE_THREADSAFE==0
# define recoverEnterMutex()
# define recoverLeaveMutex()
# define recoverAssertMutexHeld()
#else
static void recoverEnterMutex(void){
  sqlite3_mutex_enter(sqlite3_mutex_alloc(RECOVER_MUTEX_ID));
}
static void recoverLeaveMutex(void){
  sqlite3_mutex_leave(sqlite3_mutex_alloc(RECOVER_MUTEX_ID));
}
static void recoverAssertMutexHeld(void){
  assert( sqlite3_mutex_held(sqlite3_mutex_alloc(RECOVER_MUTEX_ID)) );
}
#endif


/*
** Like strlen(). But handles NULL pointer arguments.
*/
static int recoverStrlen(const char *zStr){
  int nRet = 0;
  if( zStr ){
    while( zStr[nRet] ) nRet++;
  }
  return nRet;
}

/*
** This function is a no-op if the recover handle passed as the first 
** argument already contains an error (if p->errCode!=SQLITE_OK). 
**
** Otherwise, an attempt is made to allocate, zero and return a buffer nByte
** bytes in size. If successful, a pointer to the new buffer is returned. Or,
** if an OOM error occurs, NULL is returned and the handle error code
** (p->errCode) set to SQLITE_NOMEM.
*/
static void *recoverMalloc(sqlite3_recover *p, i64 nByte){
  void *pRet = 0;
  assert( nByte>0 );
  if( p->errCode==SQLITE_OK ){
    pRet = sqlite3_malloc64(nByte);
    if( pRet ){
      memset(pRet, 0, nByte);
    }else{
      p->errCode = SQLITE_NOMEM;
    }
  }
  return pRet;
}

/*
** Set the error code and error message for the recover handle passed as
** the first argument. The error code is set to the value of parameter
** errCode.
**
** Parameter zFmt must be a printf() style formatting string. The handle 
** error message is set to the result of using any trailing arguments for 
** parameter substitutions in the formatting string.
**
** For example:
**
**   recoverError(p, SQLITE_ERROR, "no such table: %s", zTablename);
*/
static int recoverError(
  sqlite3_recover *p, 
  int errCode, 
  const char *zFmt, ...
){
  char *z = 0;
  va_list ap;
  va_start(ap, zFmt);
  if( zFmt ){
    z = sqlite3_vmprintf(zFmt, ap);
    va_end(ap);
  }
  sqlite3_free(p->zErrMsg);
  p->zErrMsg = z;
  p->errCode = errCode;
  return errCode;
}


/*
** This function is a no-op if p->errCode is initially other than SQLITE_OK.
** In this case it returns NULL.
**
** Otherwise, an attempt is made to allocate and return a bitmap object
** large enough to store a bit for all page numbers between 1 and nPg,
** inclusive. The bitmap is initially zeroed.
*/
static RecoverBitmap *recoverBitmapAlloc(sqlite3_recover *p, i64 nPg){
  int nElem = (nPg+1+31) / 32;
  int nByte = sizeof(RecoverBitmap) + nElem*sizeof(u32);
  RecoverBitmap *pRet = (RecoverBitmap*)recoverMalloc(p, nByte);

  if( pRet ){
    pRet->nPg = nPg;
  }
  return pRet;
}

/*
** Free a bitmap object allocated by recoverBitmapAlloc().
*/
static void recoverBitmapFree(RecoverBitmap *pMap){
  sqlite3_free(pMap);
}

/*
** Set the bit associated with page iPg in bitvec pMap.
*/
static void recoverBitmapSet(RecoverBitmap *pMap, i64 iPg){
  if( iPg<=pMap->nPg ){
    int iElem = (iPg / 32);
    int iBit = (iPg % 32);
    pMap->aElem[iElem] |= (((u32)1) << iBit);
  }
}

/*
** Query bitmap object pMap for the state of the bit associated with page
** iPg. Return 1 if it is set, or 0 otherwise.
*/
static int recoverBitmapQuery(RecoverBitmap *pMap, i64 iPg){
  int ret = 1;
  if( iPg<=pMap->nPg && iPg>0 ){
    int iElem = (iPg / 32);
    int iBit = (iPg % 32);
    ret = (pMap->aElem[iElem] & (((u32)1) << iBit)) ? 1 : 0;
  }
  return ret;
}

/*
** Set the recover handle error to the error code and message returned by
** calling sqlite3_errcode() and sqlite3_errmsg(), respectively, on database
** handle db.
*/
static int recoverDbError(sqlite3_recover *p, sqlite3 *db){
  return recoverError(p, sqlite3_errcode(db), "%s", sqlite3_errmsg(db));
}

/*
** This function is a no-op if recover handle p already contains an error
** (if p->errCode!=SQLITE_OK). 
**
** Otherwise, it attempts to prepare the SQL statement in zSql against
** database handle db. If successful, the statement handle is returned.
** Or, if an error occurs, NULL is returned and an error left in the
** recover handle.
*/
static sqlite3_stmt *recoverPrepare(
  sqlite3_recover *p,
  sqlite3 *db, 
  const char *zSql
){
  sqlite3_stmt *pStmt = 0;
  if( p->errCode==SQLITE_OK ){
    if( sqlite3_prepare_v2(db, zSql, -1, &pStmt, 0) ){
      recoverDbError(p, db);
    }
  }
  return pStmt;
}

/*
** This function is a no-op if recover handle p already contains an error
** (if p->errCode!=SQLITE_OK). 
**
** Otherwise, argument zFmt is used as a printf() style format string,
** along with any trailing arguments, to create an SQL statement. This
** SQL statement is prepared against database handle db and, if successful,
** the statment handle returned. Or, if an error occurs - either during
** the printf() formatting or when preparing the resulting SQL - an
** error code and message are left in the recover handle.
*/
static sqlite3_stmt *recoverPreparePrintf(
  sqlite3_recover *p,
  sqlite3 *db, 
  const char *zFmt, ...
){
  sqlite3_stmt *pStmt = 0;
  if( p->errCode==SQLITE_OK ){
    va_list ap;
    char *z;
    va_start(ap, zFmt);
    z = sqlite3_vmprintf(zFmt, ap);
    va_end(ap);
    if( z==0 ){
      p->errCode = SQLITE_NOMEM;
    }else{
      pStmt = recoverPrepare(p, db, z);
      sqlite3_free(z);
    }
  }
  return pStmt;
}

/*
** Reset SQLite statement handle pStmt. If the call to sqlite3_reset() 
** indicates that an error occurred, and there is not already an error
** in the recover handle passed as the first argument, set the error
** code and error message appropriately.
**
** This function returns a copy of the statement handle pointer passed
** as the second argument.
*/
static sqlite3_stmt *recoverReset(sqlite3_recover *p, sqlite3_stmt *pStmt){
  int rc = sqlite3_reset(pStmt);
  if( rc!=SQLITE_OK && rc!=SQLITE_CONSTRAINT && p->errCode==SQLITE_OK ){
    recoverDbError(p, sqlite3_db_handle(pStmt));
  }
  return pStmt;
}

/*
** Finalize SQLite statement handle pStmt. If the call to sqlite3_reset() 
** indicates that an error occurred, and there is not already an error
** in the recover handle passed as the first argument, set the error
** code and error message appropriately.
*/
static void recoverFinalize(sqlite3_recover *p, sqlite3_stmt *pStmt){
  sqlite3 *db = sqlite3_db_handle(pStmt);
  int rc = sqlite3_finalize(pStmt);
  if( rc!=SQLITE_OK && p->errCode==SQLITE_OK ){
    recoverDbError(p, db);
  }
}

/*
** This function is a no-op if recover handle p already contains an error
** (if p->errCode!=SQLITE_OK). A copy of p->errCode is returned in this 
** case.
**
** Otherwise, execute SQL script zSql. If successful, return SQLITE_OK.
** Or, if an error occurs, leave an error code and message in the recover
** handle and return a copy of the error code.
*/
static int recoverExec(sqlite3_recover *p, sqlite3 *db, const char *zSql){
  if( p->errCode==SQLITE_OK ){
    int rc = sqlite3_exec(db, zSql, 0, 0, 0);
    if( rc ){
      recoverDbError(p, db);
    }
  }
  return p->errCode;
}

/*
** Bind the value pVal to parameter iBind of statement pStmt. Leave an
** error in the recover handle passed as the first argument if an error
** (e.g. an OOM) occurs.
*/
static void recoverBindValue(
  sqlite3_recover *p, 
  sqlite3_stmt *pStmt, 
  int iBind, 
  sqlite3_value *pVal
){
  if( p->errCode==SQLITE_OK ){
    int rc = sqlite3_bind_value(pStmt, iBind, pVal);
    if( rc ) recoverError(p, rc, 0);
  }
}

/*
** This function is a no-op if recover handle p already contains an error
** (if p->errCode!=SQLITE_OK). NULL is returned in this case.
**
** Otherwise, an attempt is made to interpret zFmt as a printf() style
** formatting string and the result of using the trailing arguments for
** parameter substitution with it written into a buffer obtained from
** sqlite3_malloc(). If successful, a pointer to the buffer is returned.
** It is the responsibility of the caller to eventually free the buffer
** using sqlite3_free().
**
** Or, if an error occurs, an error code and message is left in the recover
** handle and NULL returned.
*/
static char *recoverMPrintf(sqlite3_recover *p, const char *zFmt, ...){
  va_list ap;
  char *z;
  va_start(ap, zFmt);
  z = sqlite3_vmprintf(zFmt, ap);
  va_end(ap);
  if( p->errCode==SQLITE_OK ){
    if( z==0 ) p->errCode = SQLITE_NOMEM;
  }else{
    sqlite3_free(z);
    z = 0;
  }
  return z;
}

/*
** This function is a no-op if recover handle p already contains an error
** (if p->errCode!=SQLITE_OK). Zero is returned in this case.
**
** Otherwise, execute "PRAGMA page_count" against the input database. If
** successful, return the integer result. Or, if an error occurs, leave an
** error code and error message in the sqlite3_recover handle and return
** zero.
*/
static i64 recoverPageCount(sqlite3_recover *p){
  i64 nPg = 0;
  if( p->errCode==SQLITE_OK ){
    sqlite3_stmt *pStmt = 0;
    pStmt = recoverPreparePrintf(p, p->dbIn, "PRAGMA %Q.page_count", p->zDb);
    if( pStmt ){
      sqlite3_step(pStmt);
      nPg = sqlite3_column_int64(pStmt, 0);
    }
    recoverFinalize(p, pStmt);
  }
  return nPg;
}

/*
** Implementation of SQL scalar function "read_i32". The first argument to 
** this function must be a blob. The second a non-negative integer. This 
** function reads and returns a 32-bit big-endian integer from byte
** offset (4*<arg2>) of the blob.
**
**     SELECT read_i32(<blob>, <idx>)
*/
static void recoverReadI32(
  sqlite3_context *context, 
  int argc, 
  sqlite3_value **argv
){
  const unsigned char *pBlob;
  int nBlob;
  int iInt;

  assert( argc==2 );
  nBlob = sqlite3_value_bytes(argv[0]);
  pBlob = (const unsigned char*)sqlite3_value_blob(argv[0]);
  iInt = sqlite3_value_int(argv[1]) & 0xFFFF;

  if( (iInt+1)*4<=nBlob ){
    const unsigned char *a = &pBlob[iInt*4];
    i64 iVal = ((i64)a[0]<<24)
             + ((i64)a[1]<<16)
             + ((i64)a[2]<< 8)
             + ((i64)a[3]<< 0);
    sqlite3_result_int64(context, iVal);
  }
}

/*
** Implementation of SQL scalar function "page_is_used". This function
** is used as part of the procedure for locating orphan rows for the
** lost-and-found table, and it depends on those routines having populated
** the sqlite3_recover.laf.pUsed variable.
**
** The only argument to this function is a page-number. It returns true 
** if the page has already been used somehow during data recovery, or false
** otherwise.
**
**     SELECT page_is_used(<pgno>);
*/
static void recoverPageIsUsed(
  sqlite3_context *pCtx,
  int nArg,
  sqlite3_value **apArg
){
  sqlite3_recover *p = (sqlite3_recover*)sqlite3_user_data(pCtx);
  i64 pgno = sqlite3_value_int64(apArg[0]);
  assert( nArg==1 );
  sqlite3_result_int(pCtx, recoverBitmapQuery(p->laf.pUsed, pgno));
}

/*
** The implementation of a user-defined SQL function invoked by the 
** sqlite_dbdata and sqlite_dbptr virtual table modules to access pages
** of the database being recovered.
**
** This function always takes a single integer argument. If the argument
** is zero, then the value returned is the number of pages in the db being
** recovered. If the argument is greater than zero, it is a page number. 
** The value returned in this case is an SQL blob containing the data for 
** the identified page of the db being recovered. e.g.
**
**     SELECT getpage(0);       -- return number of pages in db
**     SELECT getpage(4);       -- return page 4 of db as a blob of data 
*/
static void recoverGetPage(
  sqlite3_context *pCtx,
  int nArg,
  sqlite3_value **apArg
){
  sqlite3_recover *p = (sqlite3_recover*)sqlite3_user_data(pCtx);
  i64 pgno = sqlite3_value_int64(apArg[0]);
  sqlite3_stmt *pStmt = 0;

  assert( nArg==1 );
  if( pgno==0 ){
    i64 nPg = recoverPageCount(p);
    sqlite3_result_int64(pCtx, nPg);
    return;
  }else{
    if( p->pGetPage==0 ){
      pStmt = p->pGetPage = recoverPreparePrintf(
          p, p->dbIn, "SELECT data FROM sqlite_dbpage(%Q) WHERE pgno=?", p->zDb
      );
    }else if( p->errCode==SQLITE_OK ){
      pStmt = p->pGetPage;
    }

    if( pStmt ){
      sqlite3_bind_int64(pStmt, 1, pgno);
      if( SQLITE_ROW==sqlite3_step(pStmt) ){
        const u8 *aPg;
        int nPg;
        assert( p->errCode==SQLITE_OK );
        aPg = sqlite3_column_blob(pStmt, 0);
        nPg = sqlite3_column_bytes(pStmt, 0);
        if( pgno==1 && nPg==p->pgsz && 0==memcmp(p->pPage1Cache, aPg, nPg) ){
          aPg = p->pPage1Disk;
        }
        sqlite3_result_blob(pCtx, aPg, nPg-p->nReserve, SQLITE_TRANSIENT);
      }
      recoverReset(p, pStmt);
    }
  }

  if( p->errCode ){
    if( p->zErrMsg ) sqlite3_result_error(pCtx, p->zErrMsg, -1);
    sqlite3_result_error_code(pCtx, p->errCode);
  }
}

/*
** Find a string that is not found anywhere in z[].  Return a pointer
** to that string.
**
** Try to use zA and zB first.  If both of those are already found in z[]
** then make up some string and store it in the buffer zBuf.
*/
static const char *recoverUnusedString(
  const char *z,                    /* Result must not appear anywhere in z */
  const char *zA, const char *zB,   /* Try these first */
  char *zBuf                        /* Space to store a generated string */
){
  unsigned i = 0;
  if( strstr(z, zA)==0 ) return zA;
  if( strstr(z, zB)==0 ) return zB;
  do{
    sqlite3_snprintf(20,zBuf,"(%s%u)", zA, i++);
  }while( strstr(z,zBuf)!=0 );
  return zBuf;
}

/*
** Implementation of scalar SQL function "escape_crnl".  The argument passed to
** this function is the output of built-in function quote(). If the first
** character of the input is "'", indicating that the value passed to quote()
** was a text value, then this function searches the input for "\n" and "\r"
** characters and adds a wrapper similar to the following:
**
**   replace(replace(<input>, '\n', char(10), '\r', char(13));
**
** Or, if the first character of the input is not "'", then a copy of the input
** is returned.
*/
static void recoverEscapeCrnl(
  sqlite3_context *context, 
  int argc, 
  sqlite3_value **argv
){
  const char *zText = (const char*)sqlite3_value_text(argv[0]);
  if( zText && zText[0]=='\'' ){
    int nText = sqlite3_value_bytes(argv[0]);
    int i;
    char zBuf1[20];
    char zBuf2[20];
    const char *zNL = 0;
    const char *zCR = 0;
    int nCR = 0;
    int nNL = 0;

    for(i=0; zText[i]; i++){
      if( zNL==0 && zText[i]=='\n' ){
        zNL = recoverUnusedString(zText, "\\n", "\\012", zBuf1);
        nNL = (int)strlen(zNL);
      }
      if( zCR==0 && zText[i]=='\r' ){
        zCR = recoverUnusedString(zText, "\\r", "\\015", zBuf2);
        nCR = (int)strlen(zCR);
      }
    }

    if( zNL || zCR ){
      int iOut = 0;
      i64 nMax = (nNL > nCR) ? nNL : nCR;
      i64 nAlloc = nMax * nText + (nMax+64)*2;
      char *zOut = (char*)sqlite3_malloc64(nAlloc);
      if( zOut==0 ){
        sqlite3_result_error_nomem(context);
        return;
      }

      if( zNL && zCR ){
        memcpy(&zOut[iOut], "replace(replace(", 16);
        iOut += 16;
      }else{
        memcpy(&zOut[iOut], "replace(", 8);
        iOut += 8;
      }
      for(i=0; zText[i]; i++){
        if( zText[i]=='\n' ){
          memcpy(&zOut[iOut], zNL, nNL);
          iOut += nNL;
        }else if( zText[i]=='\r' ){
          memcpy(&zOut[iOut], zCR, nCR);
          iOut += nCR;
        }else{
          zOut[iOut] = zText[i];
          iOut++;
        }
      }

      if( zNL ){
        memcpy(&zOut[iOut], ",'", 2); iOut += 2;
        memcpy(&zOut[iOut], zNL, nNL); iOut += nNL;
        memcpy(&zOut[iOut], "', char(10))", 12); iOut += 12;
      }
      if( zCR ){
        memcpy(&zOut[iOut], ",'", 2); iOut += 2;
        memcpy(&zOut[iOut], zCR, nCR); iOut += nCR;
        memcpy(&zOut[iOut], "', char(13))", 12); iOut += 12;
      }

      sqlite3_result_text(context, zOut, iOut, SQLITE_TRANSIENT);
      sqlite3_free(zOut);
      return;
    }
  }

  sqlite3_result_value(context, argv[0]);
}

/*
** This function is a no-op if recover handle p already contains an error
** (if p->errCode!=SQLITE_OK). A copy of the error code is returned in
** this case. 
**
** Otherwise, attempt to populate temporary table "recovery.schema" with the
** parts of the database schema that can be extracted from the input database.
**
** If no error occurs, SQLITE_OK is returned. Otherwise, an error code
** and error message are left in the recover handle and a copy of the
** error code returned. It is not considered an error if part of all of
** the database schema cannot be recovered due to corruption.
*/
static int recoverCacheSchema(sqlite3_recover *p){
  return recoverExec(p, p->dbOut,
    "WITH RECURSIVE pages(p) AS ("
    "  SELECT 1"
    "    UNION"
    "  SELECT child FROM sqlite_dbptr('getpage()'), pages WHERE pgno=p"
    ")"
    "INSERT INTO recovery.schema SELECT"
    "  max(CASE WHEN field=0 THEN value ELSE NULL END),"
    "  max(CASE WHEN field=1 THEN value ELSE NULL END),"
    "  max(CASE WHEN field=2 THEN value ELSE NULL END),"
    "  max(CASE WHEN field=3 THEN value ELSE NULL END),"
    "  max(CASE WHEN field=4 THEN value ELSE NULL END)"
    "FROM sqlite_dbdata('getpage()') WHERE pgno IN ("
    "  SELECT p FROM pages"
    ") GROUP BY pgno, cell"
  );
}

/*
** If this recover handle is not in SQL callback mode (i.e. was not created 
** using sqlite3_recover_init_sql()) of if an error has already occurred, 
** this function is a no-op. Otherwise, issue a callback with SQL statement
** zSql as the parameter. 
**
** If the callback returns non-zero, set the recover handle error code to
** the value returned (so that the caller will abandon processing).
*/
static void recoverSqlCallback(sqlite3_recover *p, const char *zSql){
  if( p->errCode==SQLITE_OK && p->xSql ){
    int res = p->xSql(p->pSqlCtx, zSql);
    if( res ){
      recoverError(p, SQLITE_ERROR, "callback returned an error - %d", res);
    }
  }
}

/*
** Transfer the following settings from the input database to the output
** database:
**
**   + page-size,
**   + auto-vacuum settings,
**   + database encoding,
**   + user-version (PRAGMA user_version), and
**   + application-id (PRAGMA application_id), and
*/
static void recoverTransferSettings(sqlite3_recover *p){
  const char *aPragma[] = {
    "encoding",
    "page_size",
    "auto_vacuum",
    "user_version",
    "application_id"
  };
  int ii;

  /* Truncate the output database to 0 pages in size. This is done by 
  ** opening a new, empty, temp db, then using the backup API to clobber 
  ** any existing output db with a copy of it. */
  if( p->errCode==SQLITE_OK ){
    sqlite3 *db2 = 0;
    int rc = sqlite3_open("", &db2);
    if( rc!=SQLITE_OK ){
      recoverDbError(p, db2);
      return;
    }

    for(ii=0; ii<sizeof(aPragma)/sizeof(aPragma[0]); ii++){
      const char *zPrag = aPragma[ii];
      sqlite3_stmt *p1 = 0;
      p1 = recoverPreparePrintf(p, p->dbIn, "PRAGMA %Q.%s", p->zDb, zPrag);
      if( p->errCode==SQLITE_OK && sqlite3_step(p1)==SQLITE_ROW ){
        const char *zArg = (const char*)sqlite3_column_text(p1, 0);
        char *z2 = recoverMPrintf(p, "PRAGMA %s = %Q", zPrag, zArg);
        recoverSqlCallback(p, z2);
        recoverExec(p, db2, z2);
        sqlite3_free(z2);
        if( zArg==0 ){
          recoverError(p, SQLITE_NOMEM, 0);
        }
      }
      recoverFinalize(p, p1);
    }
    recoverExec(p, db2, "CREATE TABLE t1(a); DROP TABLE t1;");

    if( p->errCode==SQLITE_OK ){
      sqlite3 *db = p->dbOut;
      sqlite3_backup *pBackup = sqlite3_backup_init(db, "main", db2, "main");
      if( pBackup ){
        sqlite3_backup_step(pBackup, -1);
        p->errCode = sqlite3_backup_finish(pBackup);
      }else{
        recoverDbError(p, db);
      }
    }

    sqlite3_close(db2);
  }
}

/*
** This function is a no-op if recover handle p already contains an error
** (if p->errCode!=SQLITE_OK). A copy of the error code is returned in
** this case. 
**
** Otherwise, an attempt is made to open the output database, attach
** and create the schema of the temporary database used to store
** intermediate data, and to register all required user functions and
** virtual table modules with the output handle.
**
** If no error occurs, SQLITE_OK is returned. Otherwise, an error code
** and error message are left in the recover handle and a copy of the
** error code returned.
*/
static int recoverOpenOutput(sqlite3_recover *p){
  struct Func {
    const char *zName;
    int nArg;
    void (*xFunc)(sqlite3_context*,int,sqlite3_value **);
  } aFunc[] = {
    { "getpage", 1, recoverGetPage },
    { "page_is_used", 1, recoverPageIsUsed },
    { "read_i32", 2, recoverReadI32 },
    { "escape_crnl", 1, recoverEscapeCrnl },
  };

  const int flags = SQLITE_OPEN_URI|SQLITE_OPEN_CREATE|SQLITE_OPEN_READWRITE;
  sqlite3 *db = 0;                /* New database handle */
  int ii;                         /* For iterating through aFunc[] */

  assert( p->dbOut==0 );

  if( sqlite3_open_v2(p->zUri, &db, flags, 0) ){
    recoverDbError(p, db);
  }

  /* Register the sqlite_dbdata and sqlite_dbptr virtual table modules.
  ** These two are registered with the output database handle - this
  ** module depends on the input handle supporting the sqlite_dbpage
  ** virtual table only.  */
  if( p->errCode==SQLITE_OK ){
    p->errCode = sqlite3_dbdata_init(db, 0, 0);
  }

  /* Register the custom user-functions with the output handle. */
  for(ii=0; p->errCode==SQLITE_OK && ii<sizeof(aFunc)/sizeof(aFunc[0]); ii++){
    p->errCode = sqlite3_create_function(db, aFunc[ii].zName, 
        aFunc[ii].nArg, SQLITE_UTF8, (void*)p, aFunc[ii].xFunc, 0, 0
    );
  }

  p->dbOut = db;
  return p->errCode;
}

/*
** Attach the auxiliary database 'recovery' to the output database handle.
** This temporary database is used during the recovery process and then 
** discarded.
*/
static void recoverOpenRecovery(sqlite3_recover *p){
  char *zSql = recoverMPrintf(p, "ATTACH %Q AS recovery;", p->zStateDb);
  recoverExec(p, p->dbOut, zSql);
  recoverExec(p, p->dbOut,
      "PRAGMA writable_schema = 1;"
      "CREATE TABLE recovery.map(pgno INTEGER PRIMARY KEY, parent INT);" 
      "CREATE TABLE recovery.schema(type, name, tbl_name, rootpage, sql);"
  );
  sqlite3_free(zSql);
}


/*
** This function is a no-op if recover handle p already contains an error
** (if p->errCode!=SQLITE_OK).
**
** Otherwise, argument zName must be the name of a table that has just been
** created in the output database. This function queries the output db
** for the schema of said table, and creates a RecoverTable object to
** store the schema in memory. The new RecoverTable object is linked into
** the list at sqlite3_recover.pTblList.
**
** Parameter iRoot must be the root page of table zName in the INPUT 
** database.
*/
static void recoverAddTable(
  sqlite3_recover *p, 
  const char *zName,              /* Name of table created in output db */
  i64 iRoot                       /* Root page of same table in INPUT db */
){
  sqlite3_stmt *pStmt = recoverPreparePrintf(p, p->dbOut, 
      "PRAGMA table_xinfo(%Q)", zName
  );

  if( pStmt ){
    int iPk = -1;
    int iBind = 1;
    RecoverTable *pNew = 0;
    int nCol = 0;
    int nName = recoverStrlen(zName);
    int nByte = 0;
    while( sqlite3_step(pStmt)==SQLITE_ROW ){
      nCol++;
      nByte += (sqlite3_column_bytes(pStmt, 1)+1);
    }
    nByte += sizeof(RecoverTable) + nCol*sizeof(RecoverColumn) + nName+1;
    recoverReset(p, pStmt);

    pNew = recoverMalloc(p, nByte);
    if( pNew ){
      int i = 0;
      int iField = 0;
      char *csr = 0;
      pNew->aCol = (RecoverColumn*)&pNew[1];
      pNew->zTab = csr = (char*)&pNew->aCol[nCol];
      pNew->nCol = nCol;
      pNew->iRoot = iRoot;
      memcpy(csr, zName, nName);
      csr += nName+1;

      for(i=0; sqlite3_step(pStmt)==SQLITE_ROW; i++){
        int iPKF = sqlite3_column_int(pStmt, 5);
        int n = sqlite3_column_bytes(pStmt, 1);
        const char *z = (const char*)sqlite3_column_text(pStmt, 1);
        const char *zType = (const char*)sqlite3_column_text(pStmt, 2);
        int eHidden = sqlite3_column_int(pStmt, 6);

        if( iPk==-1 && iPKF==1 && !sqlite3_stricmp("integer", zType) ) iPk = i;
        if( iPKF>1 ) iPk = -2;
        pNew->aCol[i].zCol = csr;
        pNew->aCol[i].eHidden = eHidden;
        if( eHidden==RECOVER_EHIDDEN_VIRTUAL ){
          pNew->aCol[i].iField = -1;
        }else{
          pNew->aCol[i].iField = iField++;
        }
        if( eHidden!=RECOVER_EHIDDEN_VIRTUAL
         && eHidden!=RECOVER_EHIDDEN_STORED
        ){
          pNew->aCol[i].iBind = iBind++;
        }
        memcpy(csr, z, n);
        csr += (n+1);
      }

      pNew->pNext = p->pTblList;
      p->pTblList = pNew;
      pNew->bIntkey = 1;
    }

    recoverFinalize(p, pStmt);

    pStmt = recoverPreparePrintf(p, p->dbOut, "PRAGMA index_xinfo(%Q)", zName);
    while( pStmt && sqlite3_step(pStmt)==SQLITE_ROW ){
      int iField = sqlite3_column_int(pStmt, 0);
      int iCol = sqlite3_column_int(pStmt, 1);

      assert( iField<pNew->nCol && iCol<pNew->nCol );
      pNew->aCol[iCol].iField = iField;

      pNew->bIntkey = 0;
      iPk = -2;
    }
    recoverFinalize(p, pStmt);

    if( p->errCode==SQLITE_OK ){
      if( iPk>=0 ){
        pNew->aCol[iPk].bIPK = 1;
      }else if( pNew->bIntkey ){
        pNew->iRowidBind = iBind++;
      }
    }
  }
}

/*
** This function is called after recoverCacheSchema() has cached those parts
** of the input database schema that could be recovered in temporary table
** "recovery.schema". This function creates in the output database copies
** of all parts of that schema that must be created before the tables can
** be populated. Specifically, this means:
**
**     * all tables that are not VIRTUAL, and
**     * UNIQUE indexes.
**
** If the recovery handle uses SQL callbacks, then callbacks containing
** the associated "CREATE TABLE" and "CREATE INDEX" statements are made.
**
** Additionally, records are added to the sqlite_schema table of the
** output database for any VIRTUAL tables. The CREATE VIRTUAL TABLE
** records are written directly to sqlite_schema, not actually executed.
** If the handle is in SQL callback mode, then callbacks are invoked 
** with equivalent SQL statements.
*/
static int recoverWriteSchema1(sqlite3_recover *p){
  sqlite3_stmt *pSelect = 0;
  sqlite3_stmt *pTblname = 0;

  pSelect = recoverPrepare(p, p->dbOut,
      "WITH dbschema(rootpage, name, sql, tbl, isVirtual, isIndex) AS ("
      "  SELECT rootpage, name, sql, "
      "    type='table', "
      "    sql LIKE 'create virtual%',"
      "    (type='index' AND (sql LIKE '%unique%' OR ?1))"
      "  FROM recovery.schema"
      ")"
      "SELECT rootpage, tbl, isVirtual, name, sql"
      " FROM dbschema "
      "  WHERE tbl OR isIndex"
      "  ORDER BY tbl DESC, name=='sqlite_sequence' DESC"
  );

  pTblname = recoverPrepare(p, p->dbOut,
      "SELECT name FROM sqlite_schema "
      "WHERE type='table' ORDER BY rowid DESC LIMIT 1"
  );

  if( pSelect ){
    sqlite3_bind_int(pSelect, 1, p->bSlowIndexes);
    while( sqlite3_step(pSelect)==SQLITE_ROW ){
      i64 iRoot = sqlite3_column_int64(pSelect, 0);
      int bTable = sqlite3_column_int(pSelect, 1);
      int bVirtual = sqlite3_column_int(pSelect, 2);
      const char *zName = (const char*)sqlite3_column_text(pSelect, 3);
      const char *zSql = (const char*)sqlite3_column_text(pSelect, 4);
      char *zFree = 0;
      int rc = SQLITE_OK;

      if( bVirtual ){
        zSql = (const char*)(zFree = recoverMPrintf(p,
            "INSERT INTO sqlite_schema VALUES('table', %Q, %Q, 0, %Q)",
            zName, zName, zSql
        ));
      }
      rc = sqlite3_exec(p->dbOut, zSql, 0, 0, 0);
      if( rc==SQLITE_OK ){
        recoverSqlCallback(p, zSql);
        if( bTable && !bVirtual ){
          if( SQLITE_ROW==sqlite3_step(pTblname) ){
            const char *zTbl = (const char*)sqlite3_column_text(pTblname, 0);
            recoverAddTable(p, zTbl, iRoot);
          }
          recoverReset(p, pTblname);
        }
      }else if( rc!=SQLITE_ERROR ){
        recoverDbError(p, p->dbOut);
      }
      sqlite3_free(zFree);
    }
  }
  recoverFinalize(p, pSelect);
  recoverFinalize(p, pTblname);

  return p->errCode;
}

/*
** This function is called after the output database has been populated. It
** adds all recovered schema elements that were not created in the output
** database by recoverWriteSchema1() - everything except for tables and
** UNIQUE indexes. Specifically:
**
**     * views,
**     * triggers,
**     * non-UNIQUE indexes.
**
** If the recover handle is in SQL callback mode, then equivalent callbacks
** are issued to create the schema elements.
*/
static int recoverWriteSchema2(sqlite3_recover *p){
  sqlite3_stmt *pSelect = 0;

  pSelect = recoverPrepare(p, p->dbOut,
      p->bSlowIndexes ?
      "SELECT rootpage, sql FROM recovery.schema "
      "  WHERE type!='table' AND type!='index'"
      :
      "SELECT rootpage, sql FROM recovery.schema "
      "  WHERE type!='table' AND (type!='index' OR sql NOT LIKE '%unique%')"
  );

  if( pSelect ){
    while( sqlite3_step(pSelect)==SQLITE_ROW ){
      const char *zSql = (const char*)sqlite3_column_text(pSelect, 1);
      int rc = sqlite3_exec(p->dbOut, zSql, 0, 0, 0);
      if( rc==SQLITE_OK ){
        recoverSqlCallback(p, zSql);
      }else if( rc!=SQLITE_ERROR ){
        recoverDbError(p, p->dbOut);
      }
    }
  }
  recoverFinalize(p, pSelect);

  return p->errCode;
}

/*
** This function is a no-op if recover handle p already contains an error
** (if p->errCode!=SQLITE_OK). In this case it returns NULL.
**
** Otherwise, if the recover handle is configured to create an output
** database (was created by sqlite3_recover_init()), then this function
** prepares and returns an SQL statement to INSERT a new record into table
** pTab, assuming the first nField fields of a record extracted from disk
** are valid.
**
** For example, if table pTab is:
**
**     CREATE TABLE name(a, b GENERATED ALWAYS AS (a+1) STORED, c, d, e);
**
** And nField is 4, then the SQL statement prepared and returned is:
**
**     INSERT INTO (a, c, d) VALUES (?1, ?2, ?3);
**
** In this case even though 4 values were extracted from the input db,
** only 3 are written to the output, as the generated STORED column 
** cannot be written.
**
** If the recover handle is in SQL callback mode, then the SQL statement
** prepared is such that evaluating it returns a single row containing
** a single text value - itself an SQL statement similar to the above,
** except with SQL literals in place of the variables. For example:
**
**     SELECT 'INSERT INTO (a, c, d) VALUES (' 
**          || quote(?1) || ', '
**          || quote(?2) || ', '
**          || quote(?3) || ')';
**
** In either case, it is the responsibility of the caller to eventually
** free the statement handle using sqlite3_finalize().
*/
static sqlite3_stmt *recoverInsertStmt(
  sqlite3_recover *p, 
  RecoverTable *pTab,
  int nField
){
  sqlite3_stmt *pRet = 0;
  const char *zSep = "";
  const char *zSqlSep = "";
  char *zSql = 0;
  char *zFinal = 0;
  char *zBind = 0;
  int ii;
  int bSql = p->xSql ? 1 : 0;

  if( nField<=0 ) return 0;

  assert( nField<=pTab->nCol );

  zSql = recoverMPrintf(p, "INSERT OR IGNORE INTO %Q(", pTab->zTab);

  if( pTab->iRowidBind ){
    assert( pTab->bIntkey );
    zSql = recoverMPrintf(p, "%z_rowid_", zSql);
    if( bSql ){
      zBind = recoverMPrintf(p, "%zquote(?%d)", zBind, pTab->iRowidBind);
    }else{
      zBind = recoverMPrintf(p, "%z?%d", zBind, pTab->iRowidBind);
    }
    zSqlSep = "||', '||";
    zSep = ", ";
  }

  for(ii=0; ii<nField; ii++){
    int eHidden = pTab->aCol[ii].eHidden;
    if( eHidden!=RECOVER_EHIDDEN_VIRTUAL
     && eHidden!=RECOVER_EHIDDEN_STORED
    ){
      assert( pTab->aCol[ii].iField>=0 && pTab->aCol[ii].iBind>=1 );
      zSql = recoverMPrintf(p, "%z%s%Q", zSql, zSep, pTab->aCol[ii].zCol);

      if( bSql ){
        zBind = recoverMPrintf(p, 
            "%z%sescape_crnl(quote(?%d))", zBind, zSqlSep, pTab->aCol[ii].iBind
        );
        zSqlSep = "||', '||";
      }else{
        zBind = recoverMPrintf(p, "%z%s?%d", zBind, zSep, pTab->aCol[ii].iBind);
      }
      zSep = ", ";
    }
  }

  if( bSql ){
    zFinal = recoverMPrintf(p, "SELECT %Q || ') VALUES (' || %s || ')'", 
        zSql, zBind
    );
  }else{
    zFinal = recoverMPrintf(p, "%s) VALUES (%s)", zSql, zBind);
  }

  pRet = recoverPrepare(p, p->dbOut, zFinal);
  sqlite3_free(zSql);
  sqlite3_free(zBind);
  sqlite3_free(zFinal);
  
  return pRet;
}


/*
** Search the list of RecoverTable objects at p->pTblList for one that
** has root page iRoot in the input database. If such an object is found,
** return a pointer to it. Otherwise, return NULL.
*/
static RecoverTable *recoverFindTable(sqlite3_recover *p, u32 iRoot){
  RecoverTable *pRet = 0;
  for(pRet=p->pTblList; pRet && pRet->iRoot!=iRoot; pRet=pRet->pNext);
  return pRet;
}

/*
** This function attempts to create a lost and found table within the 
** output db. If successful, it returns a pointer to a buffer containing
** the name of the new table. It is the responsibility of the caller to
** eventually free this buffer using sqlite3_free().
**
** If an error occurs, NULL is returned and an error code and error 
** message left in the recover handle.
*/
static char *recoverLostAndFoundCreate(
  sqlite3_recover *p,             /* Recover object */
  int nField                      /* Number of column fields in new table */
){
  char *zTbl = 0;
  sqlite3_stmt *pProbe = 0;
  int ii = 0;

  pProbe = recoverPrepare(p, p->dbOut,
    "SELECT 1 FROM sqlite_schema WHERE name=?"
  );
  for(ii=-1; zTbl==0 && p->errCode==SQLITE_OK && ii<1000; ii++){
    int bFail = 0;
    if( ii<0 ){
      zTbl = recoverMPrintf(p, "%s", p->zLostAndFound);
    }else{
      zTbl = recoverMPrintf(p, "%s_%d", p->zLostAndFound, ii);
    }

    if( p->errCode==SQLITE_OK ){
      sqlite3_bind_text(pProbe, 1, zTbl, -1, SQLITE_STATIC);
      if( SQLITE_ROW==sqlite3_step(pProbe) ){
        bFail = 1;
      }
      recoverReset(p, pProbe);
    }

    if( bFail ){
      sqlite3_clear_bindings(pProbe);
      sqlite3_free(zTbl);
      zTbl = 0;
    }
  }
  recoverFinalize(p, pProbe);

  if( zTbl ){
    const char *zSep = 0;
    char *zField = 0;
    char *zSql = 0;

    zSep = "rootpgno INTEGER, pgno INTEGER, nfield INTEGER, id INTEGER, ";
    for(ii=0; p->errCode==SQLITE_OK && ii<nField; ii++){
      zField = recoverMPrintf(p, "%z%sc%d", zField, zSep, ii);
      zSep = ", ";
    }

    zSql = recoverMPrintf(p, "CREATE TABLE %s(%s)", zTbl, zField);
    sqlite3_free(zField);

    recoverExec(p, p->dbOut, zSql);
    recoverSqlCallback(p, zSql);
    sqlite3_free(zSql);
  }else if( p->errCode==SQLITE_OK ){
    recoverError(
        p, SQLITE_ERROR, "failed to create %s output table", p->zLostAndFound
    );
  }

  return zTbl;
}

/*
** Synthesize and prepare an INSERT statement to write to the lost_and_found
** table in the output database. The name of the table is zTab, and it has
** nField c* fields.
*/
static sqlite3_stmt *recoverLostAndFoundInsert(
  sqlite3_recover *p,
  const char *zTab,
  int nField
){
  int nTotal = nField + 4;
  int ii;
  char *zBind = 0;
  sqlite3_stmt *pRet = 0;

  if( p->xSql==0 ){
    for(ii=0; ii<nTotal; ii++){
      zBind = recoverMPrintf(p, "%z%s?", zBind, zBind?", ":"", ii);
    }
    pRet = recoverPreparePrintf(
        p, p->dbOut, "INSERT INTO %s VALUES(%s)", zTab, zBind
    );
  }else{
    const char *zSep = "";
    for(ii=0; ii<nTotal; ii++){
      zBind = recoverMPrintf(p, "%z%squote(?)", zBind, zSep);
      zSep = "|| ', ' ||";
    }
    pRet = recoverPreparePrintf(
        p, p->dbOut, "SELECT 'INSERT INTO %s VALUES(' || %s || ')'", zTab, zBind
    );
  }

  sqlite3_free(zBind);
  return pRet;
}

/*
** Input database page iPg contains data that will be written to the
** lost-and-found table of the output database. This function attempts
** to identify the root page of the tree that page iPg belonged to.
** If successful, it sets output variable (*piRoot) to the page number
** of the root page and returns SQLITE_OK. Otherwise, if an error occurs,
** an SQLite error code is returned and the final value of *piRoot 
** undefined.
*/
static int recoverLostAndFoundFindRoot(
  sqlite3_recover *p, 
  i64 iPg,
  i64 *piRoot
){
  RecoverStateLAF *pLaf = &p->laf;

  if( pLaf->pFindRoot==0 ){
    pLaf->pFindRoot = recoverPrepare(p, p->dbOut,
        "WITH RECURSIVE p(pgno) AS ("
        "  SELECT ?"
        "    UNION"
        "  SELECT parent FROM recovery.map AS m, p WHERE m.pgno=p.pgno"
        ") "
        "SELECT p.pgno FROM p, recovery.map m WHERE m.pgno=p.pgno "
        "    AND m.parent IS NULL"
    );
  }
  if( p->errCode==SQLITE_OK ){
    sqlite3_bind_int64(pLaf->pFindRoot, 1, iPg);
    if( sqlite3_step(pLaf->pFindRoot)==SQLITE_ROW ){
      *piRoot = sqlite3_column_int64(pLaf->pFindRoot, 0);
    }else{
      *piRoot = iPg;
    }
    recoverReset(p, pLaf->pFindRoot);
  }
  return p->errCode;
}

/*
** Recover data from page iPage of the input database and write it to
** the lost-and-found table in the output database.
*/
static void recoverLostAndFoundOnePage(sqlite3_recover *p, i64 iPage){
  RecoverStateLAF *pLaf = &p->laf;
  sqlite3_value **apVal = pLaf->apVal;
  sqlite3_stmt *pPageData = pLaf->pPageData;
  sqlite3_stmt *pInsert = pLaf->pInsert;

  int nVal = -1;
  int iPrevCell = 0;
  i64 iRoot = 0;
  int bHaveRowid = 0;
  i64 iRowid = 0;
  int ii = 0;

  if( recoverLostAndFoundFindRoot(p, iPage, &iRoot) ) return;
  sqlite3_bind_int64(pPageData, 1, iPage);
  while( p->errCode==SQLITE_OK && SQLITE_ROW==sqlite3_step(pPageData) ){
    int iCell = sqlite3_column_int64(pPageData, 0);
    int iField = sqlite3_column_int64(pPageData, 1);

    if( iPrevCell!=iCell && nVal>=0 ){
      /* Insert the new row */
      sqlite3_bind_int64(pInsert, 1, iRoot);      /* rootpgno */
      sqlite3_bind_int64(pInsert, 2, iPage);      /* pgno */
      sqlite3_bind_int(pInsert, 3, nVal);         /* nfield */
      if( bHaveRowid ){
        sqlite3_bind_int64(pInsert, 4, iRowid);   /* id */
      }
      for(ii=0; ii<nVal; ii++){
        recoverBindValue(p, pInsert, 5+ii, apVal[ii]);
      }
      if( sqlite3_step(pInsert)==SQLITE_ROW ){
        recoverSqlCallback(p, (const char*)sqlite3_column_text(pInsert, 0));
      }
      recoverReset(p, pInsert);

      /* Discard the accumulated row data */
      for(ii=0; ii<nVal; ii++){
        sqlite3_value_free(apVal[ii]);
        apVal[ii] = 0;
      }
      sqlite3_clear_bindings(pInsert);
      bHaveRowid = 0;
      nVal = -1;
    }

    if( iCell<0 ) break;

    if( iField<0 ){
      assert( nVal==-1 );
      iRowid = sqlite3_column_int64(pPageData, 2);
      bHaveRowid = 1;
      nVal = 0;
    }else if( iField<pLaf->nMaxField ){
      sqlite3_value *pVal = sqlite3_column_value(pPageData, 2);
      apVal[iField] = sqlite3_value_dup(pVal);
      assert( iField==nVal || (nVal==-1 && iField==0) );
      nVal = iField+1;
      if( apVal[iField]==0 ){
        recoverError(p, SQLITE_NOMEM, 0);
      }
    }

    iPrevCell = iCell;
  }
  recoverReset(p, pPageData);

  for(ii=0; ii<nVal; ii++){
    sqlite3_value_free(apVal[ii]);
    apVal[ii] = 0;
  }
}

/*
** Perform one step (sqlite3_recover_step()) of work for the connection 
** passed as the only argument, which is guaranteed to be in
** RECOVER_STATE_LOSTANDFOUND3 state - during which the lost-and-found 
** table of the output database is populated with recovered data that can 
** not be assigned to any recovered schema object.
*/ 
static int recoverLostAndFound3Step(sqlite3_recover *p){
  RecoverStateLAF *pLaf = &p->laf;
  if( p->errCode==SQLITE_OK ){
    if( pLaf->pInsert==0 ){
      return SQLITE_DONE;
    }else{
      if( p->errCode==SQLITE_OK ){
        int res = sqlite3_step(pLaf->pAllPage);
        if( res==SQLITE_ROW ){
          i64 iPage = sqlite3_column_int64(pLaf->pAllPage, 0);
          if( recoverBitmapQuery(pLaf->pUsed, iPage)==0 ){
            recoverLostAndFoundOnePage(p, iPage);
          }
        }else{
          recoverReset(p, pLaf->pAllPage);
          return SQLITE_DONE;
        }
      }
    }
  }
  return SQLITE_OK;
}

/*
** Initialize resources required in RECOVER_STATE_LOSTANDFOUND3 
** state - during which the lost-and-found table of the output database 
** is populated with recovered data that can not be assigned to any 
** recovered schema object.
*/ 
static void recoverLostAndFound3Init(sqlite3_recover *p){
  RecoverStateLAF *pLaf = &p->laf;

  if( pLaf->nMaxField>0 ){
    char *zTab = 0;               /* Name of lost_and_found table */

    zTab = recoverLostAndFoundCreate(p, pLaf->nMaxField);
    pLaf->pInsert = recoverLostAndFoundInsert(p, zTab, pLaf->nMaxField);
    sqlite3_free(zTab);

    pLaf->pAllPage = recoverPreparePrintf(p, p->dbOut,
        "WITH RECURSIVE seq(ii) AS ("
        "  SELECT 1 UNION ALL SELECT ii+1 FROM seq WHERE ii<%lld"
        ")"
        "SELECT ii FROM seq" , p->laf.nPg
    );
    pLaf->pPageData = recoverPrepare(p, p->dbOut,
        "SELECT cell, field, value "
        "FROM sqlite_dbdata('getpage()') d WHERE d.pgno=? "
        "UNION ALL "
        "SELECT -1, -1, -1"
    );

    pLaf->apVal = (sqlite3_value**)recoverMalloc(p, 
        pLaf->nMaxField*sizeof(sqlite3_value*)
    );
  }
}

/*
** Initialize resources required in RECOVER_STATE_WRITING state - during which
** tables recovered from the schema of the input database are populated with
** recovered data.
*/ 
static int recoverWriteDataInit(sqlite3_recover *p){
  RecoverStateW1 *p1 = &p->w1;
  RecoverTable *pTbl = 0;
  int nByte = 0;

  /* Figure out the maximum number of columns for any table in the schema */
  assert( p1->nMax==0 );
  for(pTbl=p->pTblList; pTbl; pTbl=pTbl->pNext){
    if( pTbl->nCol>p1->nMax ) p1->nMax = pTbl->nCol;
  }

  /* Allocate an array of (sqlite3_value*) in which to accumulate the values
  ** that will be written to the output database in a single row. */
  nByte = sizeof(sqlite3_value*) * (p1->nMax+1);
  p1->apVal = (sqlite3_value**)recoverMalloc(p, nByte);
  if( p1->apVal==0 ) return p->errCode;

  /* Prepare the SELECT to loop through schema tables (pTbls) and the SELECT
  ** to loop through cells that appear to belong to a single table (pSel). */
  p1->pTbls = recoverPrepare(p, p->dbOut,
      "SELECT rootpage FROM recovery.schema "
      "  WHERE type='table' AND (sql NOT LIKE 'create virtual%')"
      "  ORDER BY (tbl_name='sqlite_sequence') ASC"
  );
  p1->pSel = recoverPrepare(p, p->dbOut, 
      "WITH RECURSIVE pages(page) AS ("
      "  SELECT ?1"
      "    UNION"
      "  SELECT child FROM sqlite_dbptr('getpage()'), pages "
      "    WHERE pgno=page"
      ") "
      "SELECT page, cell, field, value "
      "FROM sqlite_dbdata('getpage()') d, pages p WHERE p.page=d.pgno "
      "UNION ALL "
      "SELECT 0, 0, 0, 0"
  );

  return p->errCode;
}

/*
** Clean up resources allocated by recoverWriteDataInit() (stuff in 
** sqlite3_recover.w1).
*/
static void recoverWriteDataCleanup(sqlite3_recover *p){
  RecoverStateW1 *p1 = &p->w1;
  int ii;
  for(ii=0; ii<p1->nVal; ii++){
    sqlite3_value_free(p1->apVal[ii]);
  }
  sqlite3_free(p1->apVal);
  recoverFinalize(p, p1->pInsert);
  recoverFinalize(p, p1->pTbls);
  recoverFinalize(p, p1->pSel);
  memset(p1, 0, sizeof(*p1));
}

/*
** Perform one step (sqlite3_recover_step()) of work for the connection 
** passed as the only argument, which is guaranteed to be in
** RECOVER_STATE_WRITING state - during which tables recovered from the
** schema of the input database are populated with recovered data.
*/ 
static int recoverWriteDataStep(sqlite3_recover *p){
  RecoverStateW1 *p1 = &p->w1;
  sqlite3_stmt *pSel = p1->pSel;
  sqlite3_value **apVal = p1->apVal;

  if( p->errCode==SQLITE_OK && p1->pTab==0 ){
    if( sqlite3_step(p1->pTbls)==SQLITE_ROW ){
      i64 iRoot = sqlite3_column_int64(p1->pTbls, 0);
      p1->pTab = recoverFindTable(p, iRoot);

      recoverFinalize(p, p1->pInsert);
      p1->pInsert = 0;

      /* If this table is unknown, return early. The caller will invoke this
      ** function again and it will move on to the next table.  */
      if( p1->pTab==0 ) return p->errCode;

      /* If this is the sqlite_sequence table, delete any rows added by
      ** earlier INSERT statements on tables with AUTOINCREMENT primary
      ** keys before recovering its contents. The p1->pTbls SELECT statement
      ** is rigged to deliver "sqlite_sequence" last of all, so we don't
      ** worry about it being modified after it is recovered. */
      if( sqlite3_stricmp("sqlite_sequence", p1->pTab->zTab)==0 ){
        recoverExec(p, p->dbOut, "DELETE FROM sqlite_sequence");
        recoverSqlCallback(p, "DELETE FROM sqlite_sequence");
      }

      /* Bind the root page of this table within the original database to 
      ** SELECT statement p1->pSel. The SELECT statement will then iterate
      ** through cells that look like they belong to table pTab.  */
      sqlite3_bind_int64(pSel, 1, iRoot);

      p1->nVal = 0;
      p1->bHaveRowid = 0;
      p1->iPrevPage = -1;
      p1->iPrevCell = -1;
    }else{
      return SQLITE_DONE;
    }
  }
  assert( p->errCode!=SQLITE_OK || p1->pTab );

  if( p->errCode==SQLITE_OK && sqlite3_step(pSel)==SQLITE_ROW ){
    RecoverTable *pTab = p1->pTab;

    i64 iPage = sqlite3_column_int64(pSel, 0);
    int iCell = sqlite3_column_int(pSel, 1);
    int iField = sqlite3_column_int(pSel, 2);
    sqlite3_value *pVal = sqlite3_column_value(pSel, 3);
    int bNewCell = (p1->iPrevPage!=iPage || p1->iPrevCell!=iCell);

    assert( bNewCell==0 || (iField==-1 || iField==0) );
    assert( bNewCell || iField==p1->nVal || p1->nVal==pTab->nCol );

    if( bNewCell ){
      int ii = 0;
      if( p1->nVal>=0 ){
        if( p1->pInsert==0 || p1->nVal!=p1->nInsert ){
          recoverFinalize(p, p1->pInsert);
          p1->pInsert = recoverInsertStmt(p, pTab, p1->nVal);
          p1->nInsert = p1->nVal;
        }
        if( p1->nVal>0 ){
          sqlite3_stmt *pInsert = p1->pInsert;
          for(ii=0; ii<pTab->nCol; ii++){
            RecoverColumn *pCol = &pTab->aCol[ii];
            int iBind = pCol->iBind;
            if( iBind>0 ){
              if( pCol->bIPK ){
                sqlite3_bind_int64(pInsert, iBind, p1->iRowid);
              }else if( pCol->iField<p1->nVal ){
                recoverBindValue(p, pInsert, iBind, apVal[pCol->iField]);
              }
            }
          }
          if( p->bRecoverRowid && pTab->iRowidBind>0 && p1->bHaveRowid ){
            sqlite3_bind_int64(pInsert, pTab->iRowidBind, p1->iRowid);
          }
          if( SQLITE_ROW==sqlite3_step(pInsert) ){
            const char *z = (const char*)sqlite3_column_text(pInsert, 0);
            recoverSqlCallback(p, z);
          }
          recoverReset(p, pInsert);
          assert( p->errCode || pInsert );
          if( pInsert ) sqlite3_clear_bindings(pInsert);
        }
      }

      for(ii=0; ii<p1->nVal; ii++){
        sqlite3_value_free(apVal[ii]);
        apVal[ii] = 0;
      }
      p1->nVal = -1;
      p1->bHaveRowid = 0;
    }

    if( iPage!=0 ){
      if( iField<0 ){
        p1->iRowid = sqlite3_column_int64(pSel, 3);
        assert( p1->nVal==-1 );
        p1->nVal = 0;
        p1->bHaveRowid = 1;
      }else if( iField<pTab->nCol ){
        assert( apVal[iField]==0 );
        apVal[iField] = sqlite3_value_dup( pVal );
        if( apVal[iField]==0 ){
          recoverError(p, SQLITE_NOMEM, 0);
        }
        p1->nVal = iField+1;
      }
      p1->iPrevCell = iCell;
      p1->iPrevPage = iPage;
    }
  }else{
    recoverReset(p, pSel);
    p1->pTab = 0;
  }

  return p->errCode;
}

/*
** Initialize resources required by sqlite3_recover_step() in
** RECOVER_STATE_LOSTANDFOUND1 state - during which the set of pages not
** already allocated to a recovered schema element is determined.
*/ 
static void recoverLostAndFound1Init(sqlite3_recover *p){
  RecoverStateLAF *pLaf = &p->laf;
  sqlite3_stmt *pStmt = 0;

  assert( p->laf.pUsed==0 );
  pLaf->nPg = recoverPageCount(p);
  pLaf->pUsed = recoverBitmapAlloc(p, pLaf->nPg);

  /* Prepare a statement to iterate through all pages that are part of any tree
  ** in the recoverable part of the input database schema to the bitmap. And,
  ** if !p->bFreelistCorrupt, add all pages that appear to be part of the
  ** freelist.  */
  pStmt = recoverPrepare(
      p, p->dbOut,
      "WITH trunk(pgno) AS ("
      "  SELECT read_i32(getpage(1), 8) AS x WHERE x>0"
      "    UNION"
      "  SELECT read_i32(getpage(trunk.pgno), 0) AS x FROM trunk WHERE x>0"
      "),"
      "trunkdata(pgno, data) AS ("
      "  SELECT pgno, getpage(pgno) FROM trunk"
      "),"
      "freelist(data, n, freepgno) AS ("
      "  SELECT data, min(16384, read_i32(data, 1)-1), pgno FROM trunkdata"
      "    UNION ALL"
      "  SELECT data, n-1, read_i32(data, 2+n) FROM freelist WHERE n>=0"
      "),"
      ""
      "roots(r) AS ("
      "  SELECT 1 UNION ALL"
      "  SELECT rootpage FROM recovery.schema WHERE rootpage>0"
      "),"
      "used(page) AS ("
      "  SELECT r FROM roots"
      "    UNION"
      "  SELECT child FROM sqlite_dbptr('getpage()'), used "
      "    WHERE pgno=page"
      ") "
      "SELECT page FROM used"
      " UNION ALL "
      "SELECT freepgno FROM freelist WHERE NOT ?"
  );
  if( pStmt ) sqlite3_bind_int(pStmt, 1, p->bFreelistCorrupt);
  pLaf->pUsedPages = pStmt;
}

/*
** Perform one step (sqlite3_recover_step()) of work for the connection 
** passed as the only argument, which is guaranteed to be in
** RECOVER_STATE_LOSTANDFOUND1 state - during which the set of pages not
** already allocated to a recovered schema element is determined.
*/ 
static int recoverLostAndFound1Step(sqlite3_recover *p){
  RecoverStateLAF *pLaf = &p->laf;
  int rc = p->errCode;
  if( rc==SQLITE_OK ){
    rc = sqlite3_step(pLaf->pUsedPages);
    if( rc==SQLITE_ROW ){
      i64 iPg = sqlite3_column_int64(pLaf->pUsedPages, 0);
      recoverBitmapSet(pLaf->pUsed, iPg);
      rc = SQLITE_OK;
    }else{
      recoverFinalize(p, pLaf->pUsedPages);
      pLaf->pUsedPages = 0;
    }
  }
  return rc;
}

/*
** Initialize resources required by RECOVER_STATE_LOSTANDFOUND2 
** state - during which the pages identified in RECOVER_STATE_LOSTANDFOUND1
** are sorted into sets that likely belonged to the same database tree.
*/ 
static void recoverLostAndFound2Init(sqlite3_recover *p){
  RecoverStateLAF *pLaf = &p->laf;

  assert( p->laf.pAllAndParent==0 );
  assert( p->laf.pMapInsert==0 );
  assert( p->laf.pMaxField==0 );
  assert( p->laf.nMaxField==0 );

  pLaf->pMapInsert = recoverPrepare(p, p->dbOut,
      "INSERT OR IGNORE INTO recovery.map(pgno, parent) VALUES(?, ?)"
  );
  pLaf->pAllAndParent = recoverPreparePrintf(p, p->dbOut,
      "WITH RECURSIVE seq(ii) AS ("
      "  SELECT 1 UNION ALL SELECT ii+1 FROM seq WHERE ii<%lld"
      ")"
      "SELECT pgno, child FROM sqlite_dbptr('getpage()') "
      " UNION ALL "
      "SELECT NULL, ii FROM seq", p->laf.nPg
  );
  pLaf->pMaxField = recoverPreparePrintf(p, p->dbOut,
      "SELECT max(field)+1 FROM sqlite_dbdata('getpage') WHERE pgno = ?"
  );
}

/*
** Perform one step (sqlite3_recover_step()) of work for the connection 
** passed as the only argument, which is guaranteed to be in
** RECOVER_STATE_LOSTANDFOUND2 state - during which the pages identified 
** in RECOVER_STATE_LOSTANDFOUND1 are sorted into sets that likely belonged 
** to the same database tree.
*/ 
static int recoverLostAndFound2Step(sqlite3_recover *p){
  RecoverStateLAF *pLaf = &p->laf;
  if( p->errCode==SQLITE_OK ){
    int res = sqlite3_step(pLaf->pAllAndParent);
    if( res==SQLITE_ROW ){
      i64 iChild = sqlite3_column_int(pLaf->pAllAndParent, 1);
      if( recoverBitmapQuery(pLaf->pUsed, iChild)==0 ){
        sqlite3_bind_int64(pLaf->pMapInsert, 1, iChild);
        sqlite3_bind_value(pLaf->pMapInsert, 2, 
            sqlite3_column_value(pLaf->pAllAndParent, 0)
        );
        sqlite3_step(pLaf->pMapInsert);
        recoverReset(p, pLaf->pMapInsert);
        sqlite3_bind_int64(pLaf->pMaxField, 1, iChild);
        if( SQLITE_ROW==sqlite3_step(pLaf->pMaxField) ){
          int nMax = sqlite3_column_int(pLaf->pMaxField, 0);
          if( nMax>pLaf->nMaxField ) pLaf->nMaxField = nMax;
        }
        recoverReset(p, pLaf->pMaxField);
      }
    }else{
      recoverFinalize(p, pLaf->pAllAndParent);
      pLaf->pAllAndParent =0;
      return SQLITE_DONE;
    }
  }
  return p->errCode;
}

/*
** Free all resources allocated as part of sqlite3_recover_step() calls
** in one of the RECOVER_STATE_LOSTANDFOUND[123] states.
*/
static void recoverLostAndFoundCleanup(sqlite3_recover *p){
  recoverBitmapFree(p->laf.pUsed);
  p->laf.pUsed = 0;
  sqlite3_finalize(p->laf.pUsedPages);
  sqlite3_finalize(p->laf.pAllAndParent);
  sqlite3_finalize(p->laf.pMapInsert);
  sqlite3_finalize(p->laf.pMaxField);
  sqlite3_finalize(p->laf.pFindRoot);
  sqlite3_finalize(p->laf.pInsert);
  sqlite3_finalize(p->laf.pAllPage);
  sqlite3_finalize(p->laf.pPageData);
  p->laf.pUsedPages = 0;
  p->laf.pAllAndParent = 0;
  p->laf.pMapInsert = 0;
  p->laf.pMaxField = 0;
  p->laf.pFindRoot = 0;
  p->laf.pInsert = 0;
  p->laf.pAllPage = 0;
  p->laf.pPageData = 0;
  sqlite3_free(p->laf.apVal);
  p->laf.apVal = 0;
}

/*
** Free all resources allocated as part of sqlite3_recover_step() calls.
*/
static void recoverFinalCleanup(sqlite3_recover *p){
  RecoverTable *pTab = 0;
  RecoverTable *pNext = 0;

  recoverWriteDataCleanup(p);
  recoverLostAndFoundCleanup(p);

  for(pTab=p->pTblList; pTab; pTab=pNext){
    pNext = pTab->pNext;
    sqlite3_free(pTab);
  }
  p->pTblList = 0;
  sqlite3_finalize(p->pGetPage);
  p->pGetPage = 0;

  {
#ifndef NDEBUG
    int res = 
#endif
       sqlite3_close(p->dbOut);
    assert( res==SQLITE_OK );
  }
  p->dbOut = 0;
}

/*
** Decode and return an unsigned 16-bit big-endian integer value from 
** buffer a[].
*/
static u32 recoverGetU16(const u8 *a){
  return (((u32)a[0])<<8) + ((u32)a[1]);
}

/*
** Decode and return an unsigned 32-bit big-endian integer value from 
** buffer a[].
*/
static u32 recoverGetU32(const u8 *a){
  return (((u32)a[0])<<24) + (((u32)a[1])<<16) + (((u32)a[2])<<8) + ((u32)a[3]);
}

/*
** Decode an SQLite varint from buffer a[]. Write the decoded value to (*pVal)
** and return the number of bytes consumed.
*/
static int recoverGetVarint(const u8 *a, i64 *pVal){
  sqlite3_uint64 u = 0;
  int i;
  for(i=0; i<8; i++){
    u = (u<<7) + (a[i]&0x7f);
    if( (a[i]&0x80)==0 ){ *pVal = (sqlite3_int64)u; return i+1; }
  }
  u = (u<<8) + (a[i]&0xff);
  *pVal = (sqlite3_int64)u;
  return 9;
}

/*
** The second argument points to a buffer n bytes in size. If this buffer
** or a prefix thereof appears to contain a well-formed SQLite b-tree page, 
** return the page-size in bytes. Otherwise, if the buffer does not 
** appear to contain a well-formed b-tree page, return 0.
*/
static int recoverIsValidPage(u8 *aTmp, const u8 *a, int n){
  u8 *aUsed = aTmp;
  int nFrag = 0;
  int nActual = 0;
  int iFree = 0;
  int nCell = 0;                  /* Number of cells on page */
  int iCellOff = 0;               /* Offset of cell array in page */
  int iContent = 0;
  int eType = 0;
  int ii = 0;

  eType = (int)a[0];
  if( eType!=0x02 && eType!=0x05 && eType!=0x0A && eType!=0x0D ) return 0;

  iFree = (int)recoverGetU16(&a[1]);
  nCell = (int)recoverGetU16(&a[3]);
  iContent = (int)recoverGetU16(&a[5]);
  if( iContent==0 ) iContent = 65536;
  nFrag = (int)a[7];

  if( iContent>n ) return 0;

  memset(aUsed, 0, n);
  memset(aUsed, 0xFF, iContent);

  /* Follow the free-list. This is the same format for all b-tree pages. */
  if( iFree && iFree<=iContent ) return 0;
  while( iFree ){
    int iNext = 0;
    int nByte = 0;
    if( iFree>(n-4) ) return 0;
    iNext = recoverGetU16(&a[iFree]);
    nByte = recoverGetU16(&a[iFree+2]);
    if( iFree+nByte>n ) return 0;
    if( iNext && iNext<iFree+nByte ) return 0;
    memset(&aUsed[iFree], 0xFF, nByte);
    iFree = iNext;
  }

  /* Run through the cells */
  if( eType==0x02 || eType==0x05 ){
    iCellOff = 12;
  }else{
    iCellOff = 8;
  }
  if( (iCellOff + 2*nCell)>iContent ) return 0;
  for(ii=0; ii<nCell; ii++){
    int iByte;
    i64 nPayload = 0;
    int nByte = 0;
    int iOff = recoverGetU16(&a[iCellOff + 2*ii]);
    if( iOff<iContent || iOff>n ){
      return 0;
    }
    if( eType==0x05 || eType==0x02 ) nByte += 4;
    nByte += recoverGetVarint(&a[iOff+nByte], &nPayload);
    if( eType==0x0D ){
      i64 dummy = 0;
      nByte += recoverGetVarint(&a[iOff+nByte], &dummy);
    }
    if( eType!=0x05 ){
      int X = (eType==0x0D) ? n-35 : (((n-12)*64/255)-23);
      int M = ((n-12)*32/255)-23;
      int K = M+((nPayload-M)%(n-4));

      if( nPayload<X ){
        nByte += nPayload;
      }else if( K<=X ){
        nByte += K+4;
      }else{
        nByte += M+4;
      }
    }

    if( iOff+nByte>n ){
      return 0;
    }
    for(iByte=iOff; iByte<(iOff+nByte); iByte++){
      if( aUsed[iByte]!=0 ){
        return 0;
      }
      aUsed[iByte] = 0xFF;
    }
  }

  nActual = 0;
  for(ii=0; ii<n; ii++){
    if( aUsed[ii]==0 ) nActual++;
  }
  return (nActual==nFrag);
}


static int recoverVfsClose(sqlite3_file*);
static int recoverVfsRead(sqlite3_file*, void*, int iAmt, sqlite3_int64 iOfst);
static int recoverVfsWrite(sqlite3_file*, const void*, int, sqlite3_int64);
static int recoverVfsTruncate(sqlite3_file*, sqlite3_int64 size);
static int recoverVfsSync(sqlite3_file*, int flags);
static int recoverVfsFileSize(sqlite3_file*, sqlite3_int64 *pSize);
static int recoverVfsLock(sqlite3_file*, int);
static int recoverVfsUnlock(sqlite3_file*, int);
static int recoverVfsCheckReservedLock(sqlite3_file*, int *pResOut);
static int recoverVfsFileControl(sqlite3_file*, int op, void *pArg);
static int recoverVfsSectorSize(sqlite3_file*);
static int recoverVfsDeviceCharacteristics(sqlite3_file*);
static int recoverVfsShmMap(sqlite3_file*, int, int, int, void volatile**);
static int recoverVfsShmLock(sqlite3_file*, int offset, int n, int flags);
static void recoverVfsShmBarrier(sqlite3_file*);
static int recoverVfsShmUnmap(sqlite3_file*, int deleteFlag);
static int recoverVfsFetch(sqlite3_file*, sqlite3_int64, int, void**);
static int recoverVfsUnfetch(sqlite3_file *pFd, sqlite3_int64 iOff, void *p);

static sqlite3_io_methods recover_methods = {
  2, /* iVersion */
  recoverVfsClose,
  recoverVfsRead,
  recoverVfsWrite,
  recoverVfsTruncate,
  recoverVfsSync,
  recoverVfsFileSize,
  recoverVfsLock,
  recoverVfsUnlock,
  recoverVfsCheckReservedLock,
  recoverVfsFileControl,
  recoverVfsSectorSize,
  recoverVfsDeviceCharacteristics,
  recoverVfsShmMap,
  recoverVfsShmLock,
  recoverVfsShmBarrier,
  recoverVfsShmUnmap,
  recoverVfsFetch,
  recoverVfsUnfetch
};

static int recoverVfsClose(sqlite3_file *pFd){
  assert( pFd->pMethods!=&recover_methods );
  return pFd->pMethods->xClose(pFd);
}

/*
** Write value v to buffer a[] as a 16-bit big-endian unsigned integer.
*/
static void recoverPutU16(u8 *a, u32 v){
  a[0] = (v>>8) & 0x00FF;
  a[1] = (v>>0) & 0x00FF;
}

/*
** Write value v to buffer a[] as a 32-bit big-endian unsigned integer.
*/
static void recoverPutU32(u8 *a, u32 v){
  a[0] = (v>>24) & 0x00FF;
  a[1] = (v>>16) & 0x00FF;
  a[2] = (v>>8) & 0x00FF;
  a[3] = (v>>0) & 0x00FF;
}

/*
** Detect the page-size of the database opened by file-handle pFd by 
** searching the first part of the file for a well-formed SQLite b-tree 
** page. If parameter nReserve is non-zero, then as well as searching for
** a b-tree page with zero reserved bytes, this function searches for one
** with nReserve reserved bytes at the end of it.
**
** If successful, set variable p->detected_pgsz to the detected page-size
** in bytes and return SQLITE_OK. Or, if no error occurs but no valid page
** can be found, return SQLITE_OK but leave p->detected_pgsz set to 0. Or,
** if an error occurs (e.g. an IO or OOM error), then an SQLite error code
** is returned. The final value of p->detected_pgsz is undefined in this
** case.
*/
static int recoverVfsDetectPagesize(
  sqlite3_recover *p,             /* Recover handle */
  sqlite3_file *pFd,              /* File-handle open on input database */
  u32 nReserve,                   /* Possible nReserve value */
  i64 nSz                         /* Size of database file in bytes */
){
  int rc = SQLITE_OK;
  const int nMin = 512;
  const int nMax = 65536;
  const int nMaxBlk = 4;
  u32 pgsz = 0;
  int iBlk = 0;
  u8 *aPg = 0;
  u8 *aTmp = 0;
  int nBlk = 0;

  aPg = (u8*)sqlite3_malloc(2*nMax);
  if( aPg==0 ) return SQLITE_NOMEM;
  aTmp = &aPg[nMax];

  nBlk = (nSz+nMax-1)/nMax;
  if( nBlk>nMaxBlk ) nBlk = nMaxBlk;

  do {
    for(iBlk=0; rc==SQLITE_OK && iBlk<nBlk; iBlk++){
      int nByte = (nSz>=((iBlk+1)*nMax)) ? nMax : (nSz % nMax);
      memset(aPg, 0, nMax);
      rc = pFd->pMethods->xRead(pFd, aPg, nByte, iBlk*nMax);
      if( rc==SQLITE_OK ){
        int pgsz2;
        for(pgsz2=(pgsz ? pgsz*2 : nMin); pgsz2<=nMax; pgsz2=pgsz2*2){
          int iOff;
          for(iOff=0; iOff<nMax; iOff+=pgsz2){
            if( recoverIsValidPage(aTmp, &aPg[iOff], pgsz2-nReserve) ){
              pgsz = pgsz2;
              break;
            }
          }
        }
      }
    }
    if( pgsz>(u32)p->detected_pgsz ){
      p->detected_pgsz = pgsz;
      p->nReserve = nReserve;
    }
    if( nReserve==0 ) break;
    nReserve = 0;
  }while( 1 );

  p->detected_pgsz = pgsz;
  sqlite3_free(aPg);
  return rc;
}

/*
** The xRead() method of the wrapper VFS. This is used to intercept calls
** to read page 1 of the input database.
*/
static int recoverVfsRead(sqlite3_file *pFd, void *aBuf, int nByte, i64 iOff){
  int rc = SQLITE_OK;
  if( pFd->pMethods==&recover_methods ){
    pFd->pMethods = recover_g.pMethods;
    rc = pFd->pMethods->xRead(pFd, aBuf, nByte, iOff);
    if( nByte==16 ){
      sqlite3_randomness(16, aBuf);
    }else
    if( rc==SQLITE_OK && iOff==0 && nByte>=108 ){
      /* Ensure that the database has a valid header file. The only fields
      ** that really matter to recovery are:
      **
      **   + Database page size (16-bits at offset 16)
      **   + Size of db in pages (32-bits at offset 28)
      **   + Database encoding (32-bits at offset 56)
      **
      ** Also preserved are:
      **
      **   + first freelist page (32-bits at offset 32)
      **   + size of freelist (32-bits at offset 36)
      **
      ** We also try to preserve the auto-vacuum, incr-value, user-version
      ** and application-id fields - all 32 bit quantities at offsets 
      ** 52, 60, 64 and 68. All other fields are set to known good values.
      **
      ** Byte offset 105 should also contain the page-size as a 16-bit 
      ** integer.
      */
      const int aPreserve[] = {32, 36, 52, 60, 64, 68};
      u8 aHdr[108] = {
        0x53, 0x51, 0x4c, 0x69, 0x74, 0x65, 0x20, 0x66, 
        0x6f, 0x72, 0x6d, 0x61, 0x74, 0x20, 0x33, 0x00,
        0xFF, 0xFF, 0x01, 0x01, 0x00, 0x40, 0x20, 0x20,
        0x00, 0x00, 0x00, 0x00, 0xFF, 0xFF, 0xFF, 0xFF,
        0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x04,
        0x00, 0x00, 0x10, 0x00, 0xFF, 0xFF, 0xFF, 0xFF,
        0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
        0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
        0x00, 0x2e, 0x5b, 0x30,

        0x0D, 0x00, 0x00, 0x00, 0x00, 0xFF, 0xFF, 0x00
      };
      u8 *a = (u8*)aBuf;

      u32 pgsz = recoverGetU16(&a[16]);
      u32 nReserve = a[20];
      u32 enc = recoverGetU32(&a[56]);
      u32 dbsz = 0;
      i64 dbFileSize = 0;
      int ii;
      sqlite3_recover *p = recover_g.p;

      if( pgsz==0x01 ) pgsz = 65536;
      rc = pFd->pMethods->xFileSize(pFd, &dbFileSize);

      if( rc==SQLITE_OK && p->detected_pgsz==0 ){
        rc = recoverVfsDetectPagesize(p, pFd, nReserve, dbFileSize);
      }
      if( p->detected_pgsz ){
        pgsz = p->detected_pgsz;
        nReserve = p->nReserve;
      }

      if( pgsz ){
        dbsz = dbFileSize / pgsz;
      }
      if( enc!=SQLITE_UTF8 && enc!=SQLITE_UTF16BE && enc!=SQLITE_UTF16LE ){
        enc = SQLITE_UTF8;
      }

      sqlite3_free(p->pPage1Cache);
      p->pPage1Cache = 0;
      p->pPage1Disk = 0;

      p->pgsz = nByte;
      p->pPage1Cache = (u8*)recoverMalloc(p, nByte*2);
      if( p->pPage1Cache ){
        p->pPage1Disk = &p->pPage1Cache[nByte];
        memcpy(p->pPage1Disk, aBuf, nByte);

        recoverPutU32(&aHdr[28], dbsz);
        recoverPutU32(&aHdr[56], enc);
        recoverPutU16(&aHdr[105], pgsz-nReserve);
        if( pgsz==65536 ) pgsz = 1;
        recoverPutU16(&aHdr[16], pgsz);
        aHdr[20] = nReserve;
        for(ii=0; ii<sizeof(aPreserve)/sizeof(aPreserve[0]); ii++){
          memcpy(&aHdr[aPreserve[ii]], &a[aPreserve[ii]], 4);
        }
        memcpy(aBuf, aHdr, sizeof(aHdr));
        memset(&((u8*)aBuf)[sizeof(aHdr)], 0, nByte-sizeof(aHdr));

        memcpy(p->pPage1Cache, aBuf, nByte);
      }else{
        rc = p->errCode;
      }

    }
    pFd->pMethods = &recover_methods;
  }else{
    rc = pFd->pMethods->xRead(pFd, aBuf, nByte, iOff);
  }
  return rc;
}

/*
** Used to make sqlite3_io_methods wrapper methods less verbose.
*/
#define RECOVER_VFS_WRAPPER(code)                         \
  int rc = SQLITE_OK;                                     \
  if( pFd->pMethods==&recover_methods ){                  \
    pFd->pMethods = recover_g.pMethods;                   \
    rc = code;                                            \
    pFd->pMethods = &recover_methods;                     \
  }else{                                                  \
    rc = code;                                            \
  }                                                       \
  return rc;                                              

/*
** Methods of the wrapper VFS. All methods except for xRead() and xClose()
** simply uninstall the sqlite3_io_methods wrapper, invoke the equivalent
** method on the lower level VFS, then reinstall the wrapper before returning.
** Those that return an integer value use the RECOVER_VFS_WRAPPER macro.
*/
static int recoverVfsWrite(
  sqlite3_file *pFd, const void *aBuf, int nByte, i64 iOff
){
  RECOVER_VFS_WRAPPER (
      pFd->pMethods->xWrite(pFd, aBuf, nByte, iOff)
  );
}
static int recoverVfsTruncate(sqlite3_file *pFd, sqlite3_int64 size){
  RECOVER_VFS_WRAPPER (
      pFd->pMethods->xTruncate(pFd, size)
  );
}
static int recoverVfsSync(sqlite3_file *pFd, int flags){
  RECOVER_VFS_WRAPPER (
      pFd->pMethods->xSync(pFd, flags)
  );
}
static int recoverVfsFileSize(sqlite3_file *pFd, sqlite3_int64 *pSize){
  RECOVER_VFS_WRAPPER (
      pFd->pMethods->xFileSize(pFd, pSize)
  );
}
static int recoverVfsLock(sqlite3_file *pFd, int eLock){
  RECOVER_VFS_WRAPPER (
      pFd->pMethods->xLock(pFd, eLock)
  );
}
static int recoverVfsUnlock(sqlite3_file *pFd, int eLock){
  RECOVER_VFS_WRAPPER (
      pFd->pMethods->xUnlock(pFd, eLock)
  );
}
static int recoverVfsCheckReservedLock(sqlite3_file *pFd, int *pResOut){
  RECOVER_VFS_WRAPPER (
      pFd->pMethods->xCheckReservedLock(pFd, pResOut)
  );
}
static int recoverVfsFileControl(sqlite3_file *pFd, int op, void *pArg){
  RECOVER_VFS_WRAPPER (
    (pFd->pMethods ?  pFd->pMethods->xFileControl(pFd, op, pArg) : SQLITE_NOTFOUND)
  );
}
static int recoverVfsSectorSize(sqlite3_file *pFd){
  RECOVER_VFS_WRAPPER (
      pFd->pMethods->xSectorSize(pFd)
  );
}
static int recoverVfsDeviceCharacteristics(sqlite3_file *pFd){
  RECOVER_VFS_WRAPPER (
      pFd->pMethods->xDeviceCharacteristics(pFd)
  );
}
static int recoverVfsShmMap(
  sqlite3_file *pFd, int iPg, int pgsz, int bExtend, void volatile **pp
){
  RECOVER_VFS_WRAPPER (
      pFd->pMethods->xShmMap(pFd, iPg, pgsz, bExtend, pp)
  );
}
static int recoverVfsShmLock(sqlite3_file *pFd, int offset, int n, int flags){
  RECOVER_VFS_WRAPPER (
      pFd->pMethods->xShmLock(pFd, offset, n, flags)
  );
}
static void recoverVfsShmBarrier(sqlite3_file *pFd){
  if( pFd->pMethods==&recover_methods ){
    pFd->pMethods = recover_g.pMethods;
    pFd->pMethods->xShmBarrier(pFd);
    pFd->pMethods = &recover_methods;
  }else{
    pFd->pMethods->xShmBarrier(pFd);
  }
}
static int recoverVfsShmUnmap(sqlite3_file *pFd, int deleteFlag){
  RECOVER_VFS_WRAPPER (
      pFd->pMethods->xShmUnmap(pFd, deleteFlag)
  );
}

static int recoverVfsFetch(
  sqlite3_file *pFd, 
  sqlite3_int64 iOff, 
  int iAmt, 
  void **pp
){
  *pp = 0;
  return SQLITE_OK;
}
static int recoverVfsUnfetch(sqlite3_file *pFd, sqlite3_int64 iOff, void *p){
  return SQLITE_OK;
}

/*
** Install the VFS wrapper around the file-descriptor open on the input
** database for recover handle p. Mutex RECOVER_MUTEX_ID must be held
** when this function is called.
*/
static void recoverInstallWrapper(sqlite3_recover *p){
  sqlite3_file *pFd = 0;
  assert( recover_g.pMethods==0 );
  recoverAssertMutexHeld();
  sqlite3_file_control(p->dbIn, p->zDb, SQLITE_FCNTL_FILE_POINTER, (void*)&pFd);
  assert( pFd==0 || pFd->pMethods!=&recover_methods );
  if( pFd && pFd->pMethods ){
    int iVersion = 1 + (pFd->pMethods->iVersion>1 && pFd->pMethods->xShmMap!=0);
    recover_g.pMethods = pFd->pMethods;
    recover_g.p = p;
    recover_methods.iVersion = iVersion;
    pFd->pMethods = &recover_methods;
  }
}

/*
** Uninstall the VFS wrapper that was installed around the file-descriptor open
** on the input database for recover handle p. Mutex RECOVER_MUTEX_ID must be
** held when this function is called.
*/
static void recoverUninstallWrapper(sqlite3_recover *p){
  sqlite3_file *pFd = 0;
  recoverAssertMutexHeld();
  sqlite3_file_control(p->dbIn, p->zDb,SQLITE_FCNTL_FILE_POINTER,(void*)&pFd);
  if( pFd && pFd->pMethods ){
    pFd->pMethods = recover_g.pMethods;
    recover_g.pMethods = 0;
    recover_g.p = 0;
  }
}

/*
** This function does the work of a single sqlite3_recover_step() call. It
** is guaranteed that the handle is not in an error state when this
** function is called.
*/
static void recoverStep(sqlite3_recover *p){
  assert( p && p->errCode==SQLITE_OK );
  switch( p->eState ){
    case RECOVER_STATE_INIT:
      /* This is the very first call to sqlite3_recover_step() on this object.
      */
      recoverSqlCallback(p, "BEGIN");
      recoverSqlCallback(p, "PRAGMA writable_schema = on");

      recoverEnterMutex();
      recoverInstallWrapper(p);

      /* Open the output database. And register required virtual tables and 
      ** user functions with the new handle. */
      recoverOpenOutput(p);

      /* Open transactions on both the input and output databases. */
      recoverExec(p, p->dbIn, "PRAGMA writable_schema = on");
      recoverExec(p, p->dbIn, "BEGIN");
      if( p->errCode==SQLITE_OK ) p->bCloseTransaction = 1;
      recoverExec(p, p->dbIn, "SELECT 1 FROM sqlite_schema");
      recoverTransferSettings(p);
      recoverOpenRecovery(p);
      recoverCacheSchema(p);

      recoverUninstallWrapper(p);
      recoverLeaveMutex();

      recoverExec(p, p->dbOut, "BEGIN");

      recoverWriteSchema1(p);
      p->eState = RECOVER_STATE_WRITING;
      break;
      
    case RECOVER_STATE_WRITING: {
      if( p->w1.pTbls==0 ){
        recoverWriteDataInit(p);
      }
      if( SQLITE_DONE==recoverWriteDataStep(p) ){
        recoverWriteDataCleanup(p);
        if( p->zLostAndFound ){
          p->eState = RECOVER_STATE_LOSTANDFOUND1;
        }else{
          p->eState = RECOVER_STATE_SCHEMA2;
        }
      }
      break;
    }

    case RECOVER_STATE_LOSTANDFOUND1: {
      if( p->laf.pUsed==0 ){
        recoverLostAndFound1Init(p);
      }
      if( SQLITE_DONE==recoverLostAndFound1Step(p) ){
        p->eState = RECOVER_STATE_LOSTANDFOUND2;
      }
      break;
    }
    case RECOVER_STATE_LOSTANDFOUND2: {
      if( p->laf.pAllAndParent==0 ){
        recoverLostAndFound2Init(p);
      }
      if( SQLITE_DONE==recoverLostAndFound2Step(p) ){
        p->eState = RECOVER_STATE_LOSTANDFOUND3;
      }
      break;
    }

    case RECOVER_STATE_LOSTANDFOUND3: {
      if( p->laf.pInsert==0 ){
        recoverLostAndFound3Init(p);
      }
      if( SQLITE_DONE==recoverLostAndFound3Step(p) ){
        p->eState = RECOVER_STATE_SCHEMA2;
      }
      break;
    }

    case RECOVER_STATE_SCHEMA2: {
      int rc = SQLITE_OK;

      recoverWriteSchema2(p);
      p->eState = RECOVER_STATE_DONE;

      /* If no error has occurred, commit the write transaction on the output
      ** database. Regardless of whether or not an error has occurred, make
      ** an attempt to end the read transaction on the input database.  */
      recoverExec(p, p->dbOut, "COMMIT");
      rc = sqlite3_exec(p->dbIn, "END", 0, 0, 0);
      if( p->errCode==SQLITE_OK ) p->errCode = rc;

      recoverSqlCallback(p, "PRAGMA writable_schema = off");
      recoverSqlCallback(p, "COMMIT");
      p->eState = RECOVER_STATE_DONE;
      recoverFinalCleanup(p);
      break;
    };

    case RECOVER_STATE_DONE: {
      /* no-op */
      break;
    };
  }
}


/*
** This is a worker function that does the heavy lifting for both init
** functions:
**
**     sqlite3_recover_init()
**     sqlite3_recover_init_sql()
**
** All this function does is allocate space for the recover handle and
** take copies of the input parameters. All the real work is done within
** sqlite3_recover_run().
*/
sqlite3_recover *recoverInit(
  sqlite3* db, 
  const char *zDb, 
  const char *zUri,               /* Output URI for _recover_init() */
  int (*xSql)(void*, const char*),/* SQL callback for _recover_init_sql() */
  void *pSqlCtx                   /* Context arg for _recover_init_sql() */
){
  sqlite3_recover *pRet = 0;
  int nDb = 0;
  int nUri = 0;
  int nByte = 0;

  if( zDb==0 ){ zDb = "main"; }

  nDb = recoverStrlen(zDb);
  nUri = recoverStrlen(zUri);

  nByte = sizeof(sqlite3_recover) + nDb+1 + nUri+1;
  pRet = (sqlite3_recover*)sqlite3_malloc(nByte);
  if( pRet ){
    memset(pRet, 0, nByte);
    pRet->dbIn = db;
    pRet->zDb = (char*)&pRet[1];
    pRet->zUri = &pRet->zDb[nDb+1];
    memcpy(pRet->zDb, zDb, nDb);
    if( nUri>0 && zUri ) memcpy(pRet->zUri, zUri, nUri);
    pRet->xSql = xSql;
    pRet->pSqlCtx = pSqlCtx;
    pRet->bRecoverRowid = RECOVER_ROWID_DEFAULT;
  }

  return pRet;
}

/*
** Initialize a recovery handle that creates a new database containing
** the recovered data.
*/
sqlite3_recover *sqlite3_recover_init(
  sqlite3* db, 
  const char *zDb, 
  const char *zUri
){
  return recoverInit(db, zDb, zUri, 0, 0);
}

/*
** Initialize a recovery handle that returns recovered data in the
** form of SQL statements via a callback.
*/
sqlite3_recover *sqlite3_recover_init_sql(
  sqlite3* db, 
  const char *zDb, 
  int (*xSql)(void*, const char*),
  void *pSqlCtx
){
  return recoverInit(db, zDb, 0, xSql, pSqlCtx);
}

/*
** Return the handle error message, if any.
*/
const char *sqlite3_recover_errmsg(sqlite3_recover *p){
  return (p && p->errCode!=SQLITE_NOMEM) ? p->zErrMsg : "out of memory";
}

/*
** Return the handle error code.
*/
int sqlite3_recover_errcode(sqlite3_recover *p){
  return p ? p->errCode : SQLITE_NOMEM;
}

/*
** Configure the handle.
*/
int sqlite3_recover_config(sqlite3_recover *p, int op, void *pArg){
  int rc = SQLITE_OK;
  if( p==0 ){
    rc = SQLITE_NOMEM;
  }else if( p->eState!=RECOVER_STATE_INIT ){
    rc = SQLITE_MISUSE;
  }else{
    switch( op ){
      case 789:
        /* This undocumented magic configuration option is used to set the
        ** name of the auxiliary database that is ATTACH-ed to the database
        ** connection and used to hold state information during the
        ** recovery process.  This option is for debugging use only and
        ** is subject to change or removal at any time. */
        sqlite3_free(p->zStateDb);
        p->zStateDb = recoverMPrintf(p, "%s", (char*)pArg);
        break;

      case SQLITE_RECOVER_LOST_AND_FOUND: {
        const char *zArg = (const char*)pArg;
        sqlite3_free(p->zLostAndFound);
        if( zArg ){
          p->zLostAndFound = recoverMPrintf(p, "%s", zArg);
        }else{
          p->zLostAndFound = 0;
        }
        break;
      }

      case SQLITE_RECOVER_FREELIST_CORRUPT:
        p->bFreelistCorrupt = *(int*)pArg;
        break;

      case SQLITE_RECOVER_ROWIDS:
        p->bRecoverRowid = *(int*)pArg;
        break;

      case SQLITE_RECOVER_SLOWINDEXES:
        p->bSlowIndexes = *(int*)pArg;
        break;

      default:
        rc = SQLITE_NOTFOUND;
        break;
    }
  }

  return rc;
}

/*
** Do a unit of work towards the recovery job. Return SQLITE_OK if
** no error has occurred but database recovery is not finished, SQLITE_DONE
** if database recovery has been successfully completed, or an SQLite
** error code if an error has occurred.
*/
int sqlite3_recover_step(sqlite3_recover *p){
  if( p==0 ) return SQLITE_NOMEM;
  if( p->errCode==SQLITE_OK ) recoverStep(p);
  if( p->eState==RECOVER_STATE_DONE && p->errCode==SQLITE_OK ){
    return SQLITE_DONE;
  }
  return p->errCode;
}

/*
** Do the configured recovery operation. Return SQLITE_OK if successful, or
** else an SQLite error code.
*/
int sqlite3_recover_run(sqlite3_recover *p){
  while( SQLITE_OK==sqlite3_recover_step(p) );
  return sqlite3_recover_errcode(p);
}


/*
** Free all resources associated with the recover handle passed as the only
** argument. The results of using a handle with any sqlite3_recover_**
** API function after it has been passed to this function are undefined.
**
** A copy of the value returned by the first call made to sqlite3_recover_run()
** on this handle is returned, or SQLITE_OK if sqlite3_recover_run() has
** not been called on this handle.
*/
int sqlite3_recover_finish(sqlite3_recover *p){
  int rc;
  if( p==0 ){
    rc = SQLITE_NOMEM;
  }else{
    recoverFinalCleanup(p);
    if( p->bCloseTransaction && sqlite3_get_autocommit(p->dbIn)==0 ){
      rc = sqlite3_exec(p->dbIn, "END", 0, 0, 0);
      if( p->errCode==SQLITE_OK ) p->errCode = rc;
    }
    rc = p->errCode;
    sqlite3_free(p->zErrMsg);
    sqlite3_free(p->zStateDb);
    sqlite3_free(p->zLostAndFound);
    sqlite3_free(p->pPage1Cache);
    sqlite3_free(p);
  }
  return rc;
}

#endif /* ifndef SQLITE_OMIT_VIRTUALTABLE */


/************************* End ../ext/recover/sqlite3recover.c ********************/
#endif

#if defined(SQLITE_ENABLE_SESSION)
/*
** State information for a single open session
*/
typedef struct OpenSession OpenSession;

  }
  len = strlen(zSql);
  if( len>78 ){
    len = 78;
    while( (zSql[len]&0xc0)==0x80 ) len--;
  }
  zCode = sqlite3_mprintf("%.*s", len, zSql);
  shell_check_oom(zCode);
  for(i=0; zCode[i]; i++){ if( IsSpace(zSql[i]) ) zCode[i] = ' '; }
  if( iOffset<25 ){
    zMsg = sqlite3_mprintf("\n  %z\n  %*s^--- error here", zCode, iOffset, "");
  }else{
    zMsg = sqlite3_mprintf("\n  %z\n  %*serror here ---^", zCode, iOffset-14, "");
  }
  return zMsg;

#ifndef SQLITE_SHELL_FIDDLE
  ".check GLOB              Fail if output since .testcase does not match",
  ".clone NEWDB             Clone data into NEWDB from the existing database",
#endif
  ".connection [close] [#]  Open or close an auxiliary database connection",
  ".databases               List names and files of attached databases",
  ".dbconfig ?op? ?val?     List or change sqlite3_db_config() options",
#if SQLITE_SHELL_HAVE_RECOVER
  ".dbinfo ?DB?             Show status information about the database",
#endif
  ".dump ?OBJECTS?          Render database content as SQL",
  "   Options:",
  "     --data-only            Output only INSERT statements",
  "     --newlines             Allow unescaped newline characters in output",
  "     --nosys                Omit system tables (ex: \"sqlite_stat1\")",

#endif
  ".prompt MAIN CONTINUE    Replace the standard prompts",
#ifndef SQLITE_SHELL_FIDDLE
  ".quit                    Exit this program",
  ".read FILE               Read input from FILE or command output",
  "    If FILE begins with \"|\", it is a command that generates the input.",
#endif
#if SQLITE_SHELL_HAVE_RECOVER
  ".recover                 Recover as much data as possible from corrupt db.",
  "   --ignore-freelist        Ignore pages that appear to be on db freelist",

  "   --lost-and-found TABLE   Alternative name for the lost-and-found table",
  "   --no-rowids              Do not attempt to recover rowid values",
  "                            that are not also INTEGER PRIMARY KEYs",
#endif
#ifndef SQLITE_SHELL_FIDDLE
  ".restore ?DB? FILE       Restore content of DB (default \"main\") from FILE",
  ".save ?OPTIONS? FILE     Write database to FILE (an alias for .backup ...)",

    sqlite3_regexp_init(p->db, 0, 0);
    sqlite3_ieee_init(p->db, 0, 0);
    sqlite3_series_init(p->db, 0, 0);
#ifndef SQLITE_SHELL_FIDDLE
    sqlite3_fileio_init(p->db, 0, 0);
    sqlite3_completion_init(p->db, 0, 0);
#endif
#if SQLITE_SHELL_HAVE_RECOVER
    sqlite3_dbdata_init(p->db, 0, 0);
#endif
#ifdef SQLITE_HAVE_ZLIB
    if( !p->bSafeModePersist ){
      sqlite3_zipfile_init(p->db, 0, 0);
      sqlite3_sqlar_init(p->db, 0, 0);
    }

    utf8_printf(p->out, "%-20s %d\n", aQuery[i].zName, val);
  }
  sqlite3_free(zSchemaTab);
  sqlite3_file_control(p->db, zDb, SQLITE_FCNTL_DATA_VERSION, &iDataVersion);
  utf8_printf(p->out, "%-20s %u\n", "data version", iDataVersion);
  return 0;
}
#endif /* SQLITE_SHELL_HAVE_RECOVER */


/*
** Print the current sqlite3_errmsg() value to stderr and return 1.
*/
static int shellDatabaseError(sqlite3 *db){
  const char *zErr = sqlite3_errmsg(db);
  utf8_printf(stderr, "Error: %s\n", zErr);

  return rc;
}
/* End of the ".archive" or ".ar" command logic
*******************************************************************************/
#endif /* !defined(SQLITE_OMIT_VIRTUALTABLE) && defined(SQLITE_HAVE_ZLIB) */























































































































































#if SQLITE_SHELL_HAVE_RECOVER















































































































































/*

** This function is used as a callback by the recover extension. Simply
** print the supplied SQL statement to stdout.
*/









static int recoverSqlCb(void *pCtx, const char *zSql){


















  ShellState *pState = (ShellState*)pCtx;



















  utf8_printf(pState->out, "%s;\n", zSql);











  return SQLITE_OK;
}

/*
** This function is called to recover data from the database. A script
** to construct a new database containing all recovered data is output
** on stream pState->out.
*/
static int recoverDatabaseCmd(ShellState *pState, int nArg, char **azArg){
  int rc = SQLITE_OK;



  const char *zRecoveryDb = "";   /* Name of "recovery" database.  Debug only */
  const char *zLAF = "lost_and_found";




  int bFreelist = 1;              /* 0 if --ignore-freelist is specified */
  int bRowids = 1;                /* 0 if --no-rowids */
  sqlite3_recover *p = 0;
  int i = 0;

  for(i=1; i<nArg; i++){
    char *z = azArg[i];
    int n;
    if( z[0]=='-' && z[1]=='-' ) z++;
    n = strlen30(z);
    if( n<=17 && memcmp("-ignore-freelist", z, n)==0 ){
      bFreelist = 0;
    }else
    if( n<=12 && memcmp("-recovery-db", z, n)==0 && i<(nArg-1) ){
      /* This option determines the name of the ATTACH-ed database used
      ** internally by the recovery extension.  The default is "" which
      ** means to use a temporary database that is automatically deleted
      ** when closed.  This option is undocumented and might disappear at
      ** any moment. */
      i++;
      zRecoveryDb = azArg[i];
    }else
    if( n<=15 && memcmp("-lost-and-found", z, n)==0 && i<(nArg-1) ){
      i++;
      zLAF = azArg[i];
    }else
    if( n<=10 && memcmp("-no-rowids", z, n)==0 ){
      bRowids = 0;
    }
    else{
      utf8_printf(stderr, "unexpected option: %s\n", azArg[i]); 
      showHelp(pState->out, azArg[0]);
      return 1;
    }
  }












  p = sqlite3_recover_init_sql(

      pState->db, "main", recoverSqlCb, (void*)pState



























































































































  );



  sqlite3_recover_config(p, 789, (void*)zRecoveryDb);  /* Debug use only */











  sqlite3_recover_config(p, SQLITE_RECOVER_LOST_AND_FOUND, (void*)zLAF);



  sqlite3_recover_config(p, SQLITE_RECOVER_ROWIDS, (void*)&bRowids);








  sqlite3_recover_config(p, SQLITE_RECOVER_FREELIST_CORRUPT,(void*)&bFreelist);




















































  sqlite3_recover_run(p);
























  if( sqlite3_recover_errcode(p)!=SQLITE_OK ){






    const char *zErr = sqlite3_recover_errmsg(p);







    int errCode = sqlite3_recover_errcode(p);

    raw_printf(stderr, "sql error: %s (%d)\n", zErr, errCode);
  }



  rc = sqlite3_recover_finish(p);





  return rc;
}
#endif /* SQLITE_SHELL_HAVE_RECOVER */


/*
 * zAutoColumn(zCol, &db, ?) => Maybe init db, add column zCol to it.
 * zAutoColumn(0, &db, ?) => (db!=0) Form columns spec for CREATE TABLE,
 *   close db and set it to 0, and return the columns spec, to later
 *   be sqlite3_free()'ed by the caller.

    }
    if( nArg>1 && ii==ArraySize(aDbConfig) ){
      utf8_printf(stderr, "Error: unknown dbconfig \"%s\"\n", azArg[1]);
      utf8_printf(stderr, "Enter \".dbconfig\" with no arguments for a list\n");
    }   
  }else

#if SQLITE_SHELL_HAVE_RECOVER
  if( c=='d' && n>=3 && cli_strncmp(azArg[0], "dbinfo", n)==0 ){
    rc = shell_dbinfo_command(p, nArg, azArg);
  }else

  if( c=='r' && cli_strncmp(azArg[0], "recover", n)==0 ){
    open_db(p, 0);
    rc = recoverDatabaseCmd(p, nArg, azArg);
  }else
#endif /* SQLITE_SHELL_HAVE_RECOVER */

  if( c=='d' && cli_strncmp(azArg[0], "dump", n)==0 ){
    char *zLike = 0;
    char *zSql;
    int i;
    int savedShowHeader = p->showHeader;
    int savedShellFlags = p->shellFlgs;

**
** See also: [sqlite3_libversion()],
** [sqlite3_libversion_number()], [sqlite3_sourceid()],
** [sqlite_version()] and [sqlite_source_id()].
*/
#define SQLITE_VERSION        "3.40.0"
#define SQLITE_VERSION_NUMBER 3040000
#define SQLITE_SOURCE_ID      "2022-11-04 16:39:39 0e5597ce5353dea2cdb092b166b57ba1d60f8115eb468349f2b2869803691a2c"

/*
** CAPI3REF: Run-Time Library Version Numbers
** KEYWORDS: sqlite3_version sqlite3_sourceid
**
** These interfaces provide the same information as the [SQLITE_VERSION],
** [SQLITE_VERSION_NUMBER], and [SQLITE_SOURCE_ID] C preprocessor macros

** A pointer to the opaque sqlite3_api_routines structure is passed as
** the third parameter to entry points of [loadable extensions].  This
** structure must be typedefed in order to work around compiler warnings
** on some platforms.
*/
typedef struct sqlite3_api_routines sqlite3_api_routines;

/*
** CAPI3REF: File Name
**
** Type [sqlite3_filename] is used by SQLite to pass filenames to the
** xOpen method of a [VFS]. It may be cast to (const char*) and treated
** as a normal, nul-terminated, UTF-8 buffer containing the filename, but
** may also be passed to special APIs such as:
**
** <ul>
** <li>  sqlite3_filename_database()
** <li>  sqlite3_filename_journal()
** <li>  sqlite3_filename_wal()
** <li>  sqlite3_uri_parameter()
** <li>  sqlite3_uri_boolean()
** <li>  sqlite3_uri_int64()
** <li>  sqlite3_uri_key()
** </ul>
*/
typedef const char *sqlite3_filename;

/*
** CAPI3REF: OS Interface Object
**
** An instance of the sqlite3_vfs object defines the interface between
** the SQLite core and the underlying operating system.  The "vfs"
** in the name of the object stands for "virtual file system".  See
** the [VFS | VFS documentation] for further information.

struct sqlite3_vfs {
  int iVersion;            /* Structure version number (currently 3) */
  int szOsFile;            /* Size of subclassed sqlite3_file */
  int mxPathname;          /* Maximum file pathname length */
  sqlite3_vfs *pNext;      /* Next registered VFS */
  const char *zName;       /* Name of this virtual file system */
  void *pAppData;          /* Pointer to application-specific data */
  int (*xOpen)(sqlite3_vfs*, sqlite3_filename zName, sqlite3_file*,
               int flags, int *pOutFlags);
  int (*xDelete)(sqlite3_vfs*, const char *zName, int syncDir);
  int (*xAccess)(sqlite3_vfs*, const char *zName, int flags, int *pResOut);
  int (*xFullPathname)(sqlite3_vfs*, const char *zName, int nOut, char *zOut);
  void *(*xDlOpen)(sqlite3_vfs*, const char *zFilename);
  void (*xDlError)(sqlite3_vfs*, int nByte, char *zErrMsg);
  void (*(*xDlSym)(sqlite3_vfs*,void*, const char *zSymbol))(void);

** routines would only work if F was the name of the main database file.
** When the F parameter is the name of the rollback journal or WAL file,
** it has access to all the same query parameters as were found on the
** main database file.
**
** See the [URI filename] documentation for additional information.
*/
SQLITE_API const char *sqlite3_uri_parameter(sqlite3_filename z, const char *zParam);
SQLITE_API int sqlite3_uri_boolean(sqlite3_filename z, const char *zParam, int bDefault);
SQLITE_API sqlite3_int64 sqlite3_uri_int64(sqlite3_filename, const char*, sqlite3_int64);
SQLITE_API const char *sqlite3_uri_key(sqlite3_filename z, int N);

/*
** CAPI3REF:  Translate filenames
**
** These routines are available to [VFS|custom VFS implementations] for
** translating filenames between the main database file, the journal file,
** and the WAL file.

** WAL file.
**
** In all of the above, if F is not the name of a database, journal or WAL
** filename passed into the VFS from the SQLite core and F is not the
** return value from [sqlite3_db_filename()], then the result is
** undefined and is likely a memory access violation.
*/
SQLITE_API const char *sqlite3_filename_database(sqlite3_filename);
SQLITE_API const char *sqlite3_filename_journal(sqlite3_filename);
SQLITE_API const char *sqlite3_filename_wal(sqlite3_filename);

/*
** CAPI3REF:  Database File Corresponding To A Journal
**
** ^If X is the name of a rollback or WAL-mode journal file that is
** passed into the xOpen method of [sqlite3_vfs], then
** sqlite3_database_file_object(X) returns a pointer to the [sqlite3_file]

** sqlite3_create_filename(), then bad things such as heap
** corruption or segfaults may occur. The value Y should not be
** used again after sqlite3_free_filename(Y) has been called.  This means
** that if the [sqlite3_vfs.xOpen()] method of a VFS has been called using Y,
** then the corresponding [sqlite3_module.xClose() method should also be
** invoked prior to calling sqlite3_free_filename(Y).
*/
SQLITE_API sqlite3_filename sqlite3_create_filename(
  const char *zDatabase,
  const char *zJournal,
  const char *zWal,
  int nParam,
  const char **azParam
);
SQLITE_API void sqlite3_free_filename(sqlite3_filename);

/*
** CAPI3REF: Error Codes And Messages
** METHOD: sqlite3
**
** ^If the most recent sqlite3_* API call associated with
** [database connection] D failed, then the sqlite3_errcode(D) interface

** <li> [sqlite3_uri_boolean()]
** <li> [sqlite3_uri_int64()]
** <li> [sqlite3_filename_database()]
** <li> [sqlite3_filename_journal()]
** <li> [sqlite3_filename_wal()]
** </ul>
*/
SQLITE_API sqlite3_filename sqlite3_db_filename(sqlite3 *db, const char *zDbName);

/*
** CAPI3REF: Determine if a database is read-only
** METHOD: sqlite3
**
** ^The sqlite3_db_readonly(D,N) interface returns 1 if the database N
** of connection D is read-only, 0 if it is read/write, or -1 if N is not

*/
struct SelectDest {
  u8 eDest;            /* How to dispose of the results.  One of SRT_* above. */
  int iSDParm;         /* A parameter used by the eDest disposal method */
  int iSDParm2;        /* A second parameter for the eDest disposal method */
  int iSdst;           /* Base register where results are written */
  int nSdst;           /* Number of registers allocated */
  char *zAffSdst;      /* Affinity used for SRT_Set, SRT_Table, and similar */
  ExprList *pOrderBy;  /* Key columns for SRT_Queue and SRT_DistQueue */
};

/*
** During code generation of statements that do inserts into AUTOINCREMENT
** tables, the following information is attached to the Table.u.autoInc.p
** pointer of each autoincrement table to record some side information that

  (u8)(((u32)(B)<(u32)0x80)?(*(A)=(unsigned char)(B)),1:\
  sqlite3PutVarint((A),(B)))
#define getVarint    sqlite3GetVarint
#define putVarint    sqlite3PutVarint


SQLITE_PRIVATE const char *sqlite3IndexAffinityStr(sqlite3*, Index*);
SQLITE_PRIVATE char *sqlite3TableAffinityStr(sqlite3*,const Table*);
SQLITE_PRIVATE void sqlite3TableAffinity(Vdbe*, Table*, int);
SQLITE_PRIVATE char sqlite3CompareAffinity(const Expr *pExpr, char aff2);
SQLITE_PRIVATE int sqlite3IndexAffinityOk(const Expr *pExpr, char idx_affinity);
SQLITE_PRIVATE char sqlite3TableColumnAffinity(const Table*,int);
SQLITE_PRIVATE char sqlite3ExprAffinity(const Expr *pExpr);
SQLITE_PRIVATE int sqlite3Atoi64(const char*, i64*, int, u8);
SQLITE_PRIVATE int sqlite3DecOrHexToI64(const char*, i64*);

  KVVfsFile *pFile = (KVVfsFile*)pProtoFile;
  unsigned int pgno;
  char zKey[30];
  char aData[131073];
  SQLITE_KV_LOG(("xWrite('%s-db',%d,%lld)\n", pFile->zClass, iAmt, iOfst));
  assert( iAmt>=512 && iAmt<=65536 );
  assert( (iAmt & (iAmt-1))==0 );
  assert( pFile->szPage<0 || pFile->szPage==iAmt );
  pFile->szPage = iAmt;
  pgno = 1 + iOfst/iAmt;
  sqlite3_snprintf(sizeof(zKey), zKey, "%u", pgno);
  kvvfsEncode(zBuf, iAmt, aData);
  if( sqlite3KvvfsMethods.xWrite(pFile->zClass, zKey, aData) ){
    return SQLITE_IOERR;
  }
  if( iOfst+iAmt > pFile->szDb ){

  sqlite3_vfs *pProtoVfs,
  const char *zName,
  sqlite3_file *pProtoFile,
  int flags,
  int *pOutFlags
){
  KVVfsFile *pFile = (KVVfsFile*)pProtoFile;
  if( zName==0 ) zName = "";
  SQLITE_KV_LOG(("xOpen(\"%s\")\n", zName));
  if( strcmp(zName, "local")==0
   || strcmp(zName, "session")==0
  ){
    pFile->isJournal = 0;
    pFile->base.pMethods = &kvvfs_db_io_methods;
  }else

        ** number of bytes in fragments may not exceed 60. */
        if( aData[hdr+7]>57 ) return 0;

        /* Remove the slot from the free-list. Update the number of
        ** fragmented bytes within the page. */
        memcpy(&aData[iAddr], &aData[pc], 2);
        aData[hdr+7] += (u8)x;

        return &aData[pc];
      }else if( x+pc > maxPC ){
        /* This slot extends off the end of the usable part of the page */
        *pRc = SQLITE_CORRUPT_PAGE(pPg);
        return 0;
      }else{
        /* The slot remains on the free-list. Reduce its size to account

  VVA_ONLY( mem1.szMalloc = 0; ) /* Only needed by assert() statements */
  assert( pPKey2->pKeyInfo->nAllField>=pPKey2->nField
       || CORRUPT_DB );
  assert( pPKey2->pKeyInfo->aSortFlags!=0 );
  assert( pPKey2->pKeyInfo->nKeyField>0 );
  assert( idx1<=szHdr1 || CORRUPT_DB );

  while( 1 /*exit-by-break*/ ){
    u32 serial_type;

    /* RHS is an integer */
    if( pRhs->flags & (MEM_Int|MEM_IntReal) ){
      testcase( pRhs->flags & MEM_Int );
      testcase( pRhs->flags & MEM_IntReal );
      serial_type = aKey1[idx1];

      return rc;
    }

    i++;
    if( i==pPKey2->nField ) break;
    pRhs++;
    d1 += sqlite3VdbeSerialTypeLen(serial_type);
    if( d1>(unsigned)nKey1 ) break;
    idx1 += sqlite3VarintLen(serial_type);
    if( idx1>=(unsigned)szHdr1 ){
      pPKey2->errCode = (u8)SQLITE_CORRUPT_BKPT;
      return 0;  /* Corrupt index */
    }
  }

  /* No memory allocation is ever used on mem1.  Prove this using
  ** the following assert().  If the assert() fails, it indicates a
  ** memory leak and a need to call sqlite3VdbeMemRelease(&mem1).  */
  assert( mem1.szMalloc==0 );

  /* rc==0 here means that one or both of the keys ran out of fields and

      pIdx->zColAff[n] = aff;
    }
    pIdx->zColAff[n] = 0;
  }

  return pIdx->zColAff;
}

/*
** Compute an affinity string for a table.   Space is obtained
** from sqlite3DbMalloc().  The caller is responsible for freeing
** the space when done.
*/
SQLITE_PRIVATE char *sqlite3TableAffinityStr(sqlite3 *db, const Table *pTab){
  char *zColAff;
  zColAff = (char *)sqlite3DbMallocRaw(db, pTab->nCol+1);
  if( zColAff ){
    int i, j;
    for(i=j=0; i<pTab->nCol; i++){
      if( (pTab->aCol[i].colFlags & COLFLAG_VIRTUAL)==0 ){
        zColAff[j++] = pTab->aCol[i].affinity;
      }
    }
    do{
      zColAff[j--] = 0;
    }while( j>=0 && zColAff[j]<=SQLITE_AFF_BLOB );
  }
  return zColAff;
}

/*
** Make changes to the evolving bytecode to do affinity transformations
** of values that are about to be gathered into a row for table pTab.
**
** For ordinary (legacy, non-strict) tables:
** -----------------------------------------

** the last opcode generated.  The new OP_TypeCheck needs to be inserted
** before the OP_MakeRecord.  The new OP_TypeCheck should use the same
** register set as the OP_MakeRecord.  If iReg>0 then register iReg is
** the first of a series of registers that will form the new record.
** Apply the type checking to that array of registers.
*/
SQLITE_PRIVATE void sqlite3TableAffinity(Vdbe *v, Table *pTab, int iReg){
  int i;
  char *zColAff;
  if( pTab->tabFlags & TF_Strict ){
    if( iReg==0 ){
      /* Move the previous opcode (which should be OP_MakeRecord) forward
      ** by one slot and insert a new OP_TypeCheck where the current
      ** OP_MakeRecord is found */
      VdbeOp *pPrev;

      sqlite3VdbeAddOp2(v, OP_TypeCheck, iReg, pTab->nNVCol);
      sqlite3VdbeAppendP4(v, pTab, P4_TABLE);
    }
    return;
  }
  zColAff = pTab->zColAff;
  if( zColAff==0 ){
    zColAff = sqlite3TableAffinityStr(0, pTab);

    if( !zColAff ){
      sqlite3OomFault(sqlite3VdbeDb(v));
      return;
    }










    pTab->zColAff = zColAff;
  }
  assert( zColAff!=0 );
  i = sqlite3Strlen30NN(zColAff);
  if( i ){
    if( iReg ){
      sqlite3VdbeAddOp4(v, OP_Affinity, iReg, i, 0, zColAff, i);

  /* Version 3.31.0 and later */
  sqlite3_int64 (*hard_heap_limit64)(sqlite3_int64);
  const char *(*uri_key)(const char*,int);
  const char *(*filename_database)(const char*);
  const char *(*filename_journal)(const char*);
  const char *(*filename_wal)(const char*);
  /* Version 3.32.0 and later */
  const char *(*create_filename)(const char*,const char*,const char*,
                           int,const char**);
  void (*free_filename)(const char*);
  sqlite3_file *(*database_file_object)(const char*);
  /* Version 3.34.0 and later */
  int (*txn_state)(sqlite3*,const char*);
  /* Version 3.36.1 and later */
  sqlite3_int64 (*changes64)(sqlite3*);
  sqlite3_int64 (*total_changes64)(sqlite3*);
  /* Version 3.37.0 and later */

    case SRT_EphemTab: {
      int r1 = sqlite3GetTempRange(pParse, nPrefixReg+1);
      testcase( eDest==SRT_Table );
      testcase( eDest==SRT_EphemTab );
      testcase( eDest==SRT_Fifo );
      testcase( eDest==SRT_DistFifo );
      sqlite3VdbeAddOp3(v, OP_MakeRecord, regResult, nResultCol, r1+nPrefixReg);
      if( pDest->zAffSdst ){
        sqlite3VdbeChangeP4(v, -1, pDest->zAffSdst, nResultCol);
      }
#ifndef SQLITE_OMIT_CTE
      if( eDest==SRT_DistFifo ){
        /* If the destination is DistFifo, then cursor (iParm+1) is open
        ** on an ephemeral index. If the current row is already present
        ** in the index, do not write it to the output. If not, add the
        ** current row to the index and proceed with writing it to the
        ** output table as well.  */

**              (17d1) aggregate, or
**              (17d2) DISTINCT
**        (17e) the subquery may not contain window functions, and
**        (17f) the subquery must not be the RHS of a LEFT JOIN.
**        (17g) either the subquery is the first element of the outer
**              query or there are no RIGHT or FULL JOINs in any arm
**              of the subquery.  (This is a duplicate of condition (27b).)
**        (17h) The corresponding result set expressions in all arms of the
**              compound must have the same affinity.
**
**        The parent and sub-query may contain WHERE clauses. Subject to
**        rules (11), (13) and (14), they may also contain ORDER BY,
**        LIMIT and OFFSET clauses.  The subquery cannot use any compound
**        operator other than UNION ALL because all the other compound
**        operators have an implied DISTINCT which is disallowed by
**        restriction (4).

  /* Restriction (17): If the sub-query is a compound SELECT, then it must
  ** use only the UNION ALL operator. And none of the simple select queries
  ** that make up the compound SELECT are allowed to be aggregate or distinct
  ** queries.
  */
  if( pSub->pPrior ){
    int ii;
    if( pSub->pOrderBy ){
      return 0;  /* Restriction (20) */
    }
    if( isAgg || (p->selFlags & SF_Distinct)!=0 || isOuterJoin>0 ){
      return 0; /* (17d1), (17d2), or (17f) */
    }
    for(pSub1=pSub; pSub1; pSub1=pSub1->pPrior){

        return 0;   /* Restrictions (17g), (27b) */
      }
      testcase( pSub1->pSrc->nSrc>1 );
    }

    /* Restriction (18). */
    if( p->pOrderBy ){

      for(ii=0; ii<p->pOrderBy->nExpr; ii++){
        if( p->pOrderBy->a[ii].u.x.iOrderByCol==0 ) return 0;
      }
    }

    /* Restriction (23) */
    if( (p->selFlags & SF_Recursive) ) return 0;

    /* Restriction (17h) */
    for(ii=0; ii<pSub->pEList->nExpr; ii++){
      char aff;
      assert( pSub->pEList->a[ii].pExpr!=0 );
      aff = sqlite3ExprAffinity(pSub->pEList->a[ii].pExpr);
      for(pSub1=pSub->pPrior; pSub1; pSub1=pSub1->pPrior){
        assert( pSub1->pEList!=0 );
        assert( pSub1->pEList->nExpr>ii );
        assert( pSub1->pEList->a[ii].pExpr!=0 );
        if( sqlite3ExprAffinity(pSub1->pEList->a[ii].pExpr)!=aff ){
          return 0;
        }
      }
    }

    if( pSrc->nSrc>1 ){
      if( pParse->nSelect>500 ) return 0;
      if( OptimizationDisabled(db, SQLITE_FlttnUnionAll) ) return 0;
      aCsrMap = sqlite3DbMallocZero(db, ((i64)pParse->nTab+1)*sizeof(int));
      if( aCsrMap ) aCsrMap[0] = pParse->nTab;
    }

**          all window-functions used by the sub-query. It is safe to
**          filter out entire partitions, as this does not change the
**          window over which any window-function is calculated.
**
**   (7) The inner query is a Common Table Expression (CTE) that should
**       be materialized.  (This restriction is implemented in the calling
**       routine.)
**
**   (8) The subquery may not be a compound that uses UNION, INTERSECT,
**       or EXCEPT.  (We could, perhaps, relax this restriction to allow
**       this case if none of the comparisons operators between left and
**       right arms of the compound use a collation other than BINARY.
**       But it is a lot of work to check that case for an obscure and
**       minor optimization, so we omit it for now.)
**
** Return 0 if no changes are made and non-zero if one or more WHERE clause
** terms are duplicated into the subquery.
*/
static int pushDownWhereTerms(
  Parse *pParse,        /* Parse context (for malloc() and error reporting) */
  Select *pSubq,        /* The subquery whose WHERE clause is to be augmented */
  Expr *pWhere,         /* The WHERE clause of the outer query */
  SrcItem *pSrc         /* The subquery term of the outer FROM clause */
){
  Expr *pNew;
  int nChng = 0;
  if( pWhere==0 ) return 0;
  if( pSubq->selFlags & (SF_Recursive|SF_MultiPart) ) return 0;
  if( pSrc->fg.jointype & (JT_LTORJ|JT_RIGHT) ) return 0;

#ifndef SQLITE_OMIT_WINDOWFUNC
  if( pSubq->pPrior ){
    Select *pSel;
    for(pSel=pSubq; pSel; pSel=pSel->pPrior){
      u8 op = pSel->op;
      assert( op==TK_ALL || op==TK_SELECT
           || op==TK_UNION || op==TK_INTERSECT || op==TK_EXCEPT );
      if( op!=TK_ALL && op!=TK_SELECT ) return 0;  /* restriction (8) */
      if( pSel->pWin ) return 0;    /* restriction (6b) */
    }
  }else{
    if( pSubq->pWin && pSubq->pWin->pPartition==0 ) return 0;
  }
#endif

        onceAddr = sqlite3VdbeAddOp0(v, OP_Once); VdbeCoverage(v);
        VdbeComment((v, "materialize %!S", pItem));
      }else{
        VdbeNoopComment((v, "materialize %!S", pItem));
      }
      sqlite3SelectDestInit(&dest, SRT_EphemTab, pItem->iCursor);
      ExplainQueryPlan((pParse, 1, "MATERIALIZE %!S", pItem));
      dest.zAffSdst = sqlite3TableAffinityStr(db, pItem->pTab);
      sqlite3Select(pParse, pSub, &dest);
      sqlite3DbFree(db, dest.zAffSdst);
      dest.zAffSdst = 0;
      pItem->pTab->nRowLogEst = pSub->nSelectRow;
      if( onceAddr ) sqlite3VdbeJumpHere(v, onceAddr);
      sqlite3VdbeAddOp2(v, OP_Return, pItem->regReturn, topAddr+1);
      VdbeComment((v, "end %!S", pItem));
      sqlite3VdbeJumpHere(v, topAddr);
      sqlite3ClearTempRegCache(pParse);
      if( pItem->fg.isCte && pItem->fg.isCorrelated==0 ){

  }
  if( rc!=SQLITE_OK ){
    if( rc==SQLITE_NOMEM ) sqlite3OomFault(db);
    sqlite3ErrorWithMsg(db, rc, zErrMsg ? "%s" : 0, zErrMsg);
    sqlite3_free(zErrMsg);
    goto opendb_out;
  }
  assert( db->pVfs!=0 );
#if SQLITE_OS_KV || defined(SQLITE_OS_KV_OPTIONAL)
  if( sqlite3_stricmp(db->pVfs->zName, "kvvfs")==0 ){
    db->temp_store = 2;
  }
#endif

  /* Open the backend database driver */
  rc = sqlite3BtreeOpen(db->pVfs, zOpen, db, &db->aDb[0].pBt, 0,
                        flags | SQLITE_OPEN_MAIN_DB);
  if( rc!=SQLITE_OK ){
    if( rc==SQLITE_IOERR_NOMEM ){
      rc = SQLITE_NOMEM_BKPT;

** and query parameters.  The pointer returned is valid for use by
** sqlite3_filename_database() and sqlite3_uri_parameter() and related
** functions.
**
** Memory layout must be compatible with that generated by the pager
** and expected by sqlite3_uri_parameter() and databaseName().
*/
SQLITE_API const char *sqlite3_create_filename(
  const char *zDatabase,
  const char *zJournal,
  const char *zWal,
  int nParam,
  const char **azParam
){
  sqlite3_int64 nByte;

}

/*
** Free memory obtained from sqlite3_create_filename().  It is a severe
** error to call this routine with any parameter other than a pointer
** previously obtained from sqlite3_create_filename() or a NULL pointer.
*/
SQLITE_API void sqlite3_free_filename(const char *p){
  if( p==0 ) return;
  p = databaseName(p);
  sqlite3_free((char*)p - 4);
}


/*
** This is a utility routine, useful to VFS implementations, that checks
** to see if a database file was a URI that contained a specific query
** parameter, and if so obtains the value of the query parameter.

  switch( i ){
    case 0: {           /* pgno */
      sqlite3_result_int(ctx, pCsr->pgno);
      break;
    }
    case 1: {           /* data */
      DbPage *pDbPage = 0;
      if( pCsr->pgno==((PENDING_BYTE/pCsr->szPage)+1) ){
        /* The pending byte page. Assume it is zeroed out. Attempting to
        ** request this page from the page is an SQLITE_CORRUPT error. */
        sqlite3_result_zeroblob(ctx, pCsr->szPage);
      }else{
        rc = sqlite3PagerGet(pCsr->pPager, pCsr->pgno, (DbPage**)&pDbPage, 0);
        if( rc==SQLITE_OK ){
          sqlite3_result_blob(ctx, sqlite3PagerGetData(pDbPage), pCsr->szPage,
              SQLITE_TRANSIENT);
        }
        sqlite3PagerUnref(pDbPage);
      }
      break;
    }
    default: {          /* schema */
      sqlite3 *db = sqlite3_context_db_handle(ctx);
      sqlite3_result_text(ctx, db->aDb[pCsr->iDb].zDbSName, -1, SQLITE_STATIC);
      break;
    }
  }
  return rc;
}

static int dbpageRowid(sqlite3_vtab_cursor *pCursor, sqlite_int64 *pRowid){
  DbpageCursor *pCsr = (DbpageCursor *)pCursor;
  *pRowid = pCsr->pgno;
  return SQLITE_OK;
}

  ){
    zErr = "bad page value";
    goto update_fail;
  }
  pPager = sqlite3BtreePager(pBt);
  rc = sqlite3PagerGet(pPager, pgno, (DbPage**)&pDbPage, 0);
  if( rc==SQLITE_OK ){
    const void *pData = sqlite3_value_blob(argv[3]);
    assert( pData!=0 || pTab->db->mallocFailed );
    if( pData
     && (rc = sqlite3PagerWrite(pDbPage))==SQLITE_OK
    ){
      memcpy(sqlite3PagerGetData(pDbPage), pData, szPage);


    }
  }
  sqlite3PagerUnref(pDbPage);
  return rc;

update_fail:
  sqlite3_free(pVtab->zErrMsg);

static void fts5SourceIdFunc(
  sqlite3_context *pCtx,          /* Function call context */
  int nArg,                       /* Number of args */
  sqlite3_value **apUnused        /* Function arguments */
){
  assert( nArg==0 );
  UNUSED_PARAM2(nArg, apUnused);
  sqlite3_result_text(pCtx, "fts5: 2022-11-04 16:39:39 0e5597ce5353dea2cdb092b166b57ba1d60f8115eb468349f2b2869803691a2c", -1, SQLITE_TRANSIENT);
}

/*
** Return true if zName is the extension on one of the shadow tables used
** by this module.
*/
static int fts5ShadowName(const char *zName){

**
** See also: [sqlite3_libversion()],
** [sqlite3_libversion_number()], [sqlite3_sourceid()],
** [sqlite_version()] and [sqlite_source_id()].
*/
#define SQLITE_VERSION        "3.40.0"
#define SQLITE_VERSION_NUMBER 3040000
#define SQLITE_SOURCE_ID      "2022-11-04 16:39:39 0e5597ce5353dea2cdb092b166b57ba1d60f8115eb468349f2b2869803691a2c"

/*
** CAPI3REF: Run-Time Library Version Numbers
** KEYWORDS: sqlite3_version sqlite3_sourceid
**
** These interfaces provide the same information as the [SQLITE_VERSION],
** [SQLITE_VERSION_NUMBER], and [SQLITE_SOURCE_ID] C preprocessor macros

** A pointer to the opaque sqlite3_api_routines structure is passed as
** the third parameter to entry points of [loadable extensions].  This
** structure must be typedefed in order to work around compiler warnings
** on some platforms.
*/
typedef struct sqlite3_api_routines sqlite3_api_routines;

/*
** CAPI3REF: File Name
**
** Type [sqlite3_filename] is used by SQLite to pass filenames to the
** xOpen method of a [VFS]. It may be cast to (const char*) and treated
** as a normal, nul-terminated, UTF-8 buffer containing the filename, but
** may also be passed to special APIs such as:
**
** <ul>
** <li>  sqlite3_filename_database()
** <li>  sqlite3_filename_journal()
** <li>  sqlite3_filename_wal()
** <li>  sqlite3_uri_parameter()
** <li>  sqlite3_uri_boolean()
** <li>  sqlite3_uri_int64()
** <li>  sqlite3_uri_key()
** </ul>
*/
typedef const char *sqlite3_filename;

/*
** CAPI3REF: OS Interface Object
**
** An instance of the sqlite3_vfs object defines the interface between
** the SQLite core and the underlying operating system.  The "vfs"
** in the name of the object stands for "virtual file system".  See
** the [VFS | VFS documentation] for further information.

struct sqlite3_vfs {
  int iVersion;            /* Structure version number (currently 3) */
  int szOsFile;            /* Size of subclassed sqlite3_file */
  int mxPathname;          /* Maximum file pathname length */
  sqlite3_vfs *pNext;      /* Next registered VFS */
  const char *zName;       /* Name of this virtual file system */
  void *pAppData;          /* Pointer to application-specific data */
  int (*xOpen)(sqlite3_vfs*, sqlite3_filename zName, sqlite3_file*,
               int flags, int *pOutFlags);
  int (*xDelete)(sqlite3_vfs*, const char *zName, int syncDir);
  int (*xAccess)(sqlite3_vfs*, const char *zName, int flags, int *pResOut);
  int (*xFullPathname)(sqlite3_vfs*, const char *zName, int nOut, char *zOut);
  void *(*xDlOpen)(sqlite3_vfs*, const char *zFilename);
  void (*xDlError)(sqlite3_vfs*, int nByte, char *zErrMsg);
  void (*(*xDlSym)(sqlite3_vfs*,void*, const char *zSymbol))(void);

** routines would only work if F was the name of the main database file.
** When the F parameter is the name of the rollback journal or WAL file,
** it has access to all the same query parameters as were found on the
** main database file.
**
** See the [URI filename] documentation for additional information.
*/
SQLITE_API const char *sqlite3_uri_parameter(sqlite3_filename z, const char *zParam);
SQLITE_API int sqlite3_uri_boolean(sqlite3_filename z, const char *zParam, int bDefault);
SQLITE_API sqlite3_int64 sqlite3_uri_int64(sqlite3_filename, const char*, sqlite3_int64);
SQLITE_API const char *sqlite3_uri_key(sqlite3_filename z, int N);

/*
** CAPI3REF:  Translate filenames
**
** These routines are available to [VFS|custom VFS implementations] for
** translating filenames between the main database file, the journal file,
** and the WAL file.

** WAL file.
**
** In all of the above, if F is not the name of a database, journal or WAL
** filename passed into the VFS from the SQLite core and F is not the
** return value from [sqlite3_db_filename()], then the result is
** undefined and is likely a memory access violation.
*/
SQLITE_API const char *sqlite3_filename_database(sqlite3_filename);
SQLITE_API const char *sqlite3_filename_journal(sqlite3_filename);
SQLITE_API const char *sqlite3_filename_wal(sqlite3_filename);

/*
** CAPI3REF:  Database File Corresponding To A Journal
**
** ^If X is the name of a rollback or WAL-mode journal file that is
** passed into the xOpen method of [sqlite3_vfs], then
** sqlite3_database_file_object(X) returns a pointer to the [sqlite3_file]

** sqlite3_create_filename(), then bad things such as heap
** corruption or segfaults may occur. The value Y should not be
** used again after sqlite3_free_filename(Y) has been called.  This means
** that if the [sqlite3_vfs.xOpen()] method of a VFS has been called using Y,
** then the corresponding [sqlite3_module.xClose() method should also be
** invoked prior to calling sqlite3_free_filename(Y).
*/
SQLITE_API sqlite3_filename sqlite3_create_filename(
  const char *zDatabase,
  const char *zJournal,
  const char *zWal,
  int nParam,
  const char **azParam
);
SQLITE_API void sqlite3_free_filename(sqlite3_filename);

/*
** CAPI3REF: Error Codes And Messages
** METHOD: sqlite3
**
** ^If the most recent sqlite3_* API call associated with
** [database connection] D failed, then the sqlite3_errcode(D) interface

** <li> [sqlite3_uri_boolean()]
** <li> [sqlite3_uri_int64()]
** <li> [sqlite3_filename_database()]
** <li> [sqlite3_filename_journal()]
** <li> [sqlite3_filename_wal()]
** </ul>
*/
SQLITE_API sqlite3_filename sqlite3_db_filename(sqlite3 *db, const char *zDbName);

/*
** CAPI3REF: Determine if a database is read-only
** METHOD: sqlite3
**
** ^The sqlite3_db_readonly(D,N) interface returns 1 if the database N
** of connection D is read-only, 0 if it is read/write, or -1 if N is not