xref: /sqlite-3.40.0/src/build.c (revision af94adf0)

/*
** 2001 September 15
**
** 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 C code routines that are called by the SQLite parser
** when syntax rules are reduced.  The routines in this file handle the
** following kinds of SQL syntax:
**
**     CREATE TABLE
**     DROP TABLE
**     CREATE INDEX
**     DROP INDEX
**     creating ID lists
**     BEGIN TRANSACTION
**     COMMIT
**     ROLLBACK
*/
#include "sqliteInt.h"

#ifndef SQLITE_OMIT_SHARED_CACHE
/*
** The TableLock structure is only used by the sqlite3TableLock() and
** codeTableLocks() functions.
*/
struct TableLock {
  int iDb;               /* The database containing the table to be locked */
  int iTab;              /* The root page of the table to be locked */
  u8 isWriteLock;        /* True for write lock.  False for a read lock */
  const char *zLockName; /* Name of the table */
};

/*
** Record the fact that we want to lock a table at run-time.
**
** The table to be locked has root page iTab and is found in database iDb.
** A read or a write lock can be taken depending on isWritelock.
**
** This routine just records the fact that the lock is desired.  The
** code to make the lock occur is generated by a later call to
** codeTableLocks() which occurs during sqlite3FinishCoding().
*/
void sqlite3TableLock(
  Parse *pParse,     /* Parsing context */
  int iDb,           /* Index of the database containing the table to lock */
  int iTab,          /* Root page number of the table to be locked */
  u8 isWriteLock,    /* True for a write lock */
  const char *zName  /* Name of the table to be locked */
){
  Parse *pToplevel = sqlite3ParseToplevel(pParse);
  int i;
  int nBytes;
  TableLock *p;
  assert( iDb>=0 );

  if( iDb==1 ) return;
  if( !sqlite3BtreeSharable(pParse->db->aDb[iDb].pBt) ) return;
  for(i=0; i<pToplevel->nTableLock; i++){
    p = &pToplevel->aTableLock[i];
    if( p->iDb==iDb && p->iTab==iTab ){
      p->isWriteLock = (p->isWriteLock || isWriteLock);
      return;
    }
  }

  nBytes = sizeof(TableLock) * (pToplevel->nTableLock+1);
  pToplevel->aTableLock =
      sqlite3DbReallocOrFree(pToplevel->db, pToplevel->aTableLock, nBytes);
  if( pToplevel->aTableLock ){
    p = &pToplevel->aTableLock[pToplevel->nTableLock++];
    p->iDb = iDb;
    p->iTab = iTab;
    p->isWriteLock = isWriteLock;
    p->zLockName = zName;
  }else{
    pToplevel->nTableLock = 0;
    sqlite3OomFault(pToplevel->db);
  }
}

/*
** Code an OP_TableLock instruction for each table locked by the
** statement (configured by calls to sqlite3TableLock()).
*/
static void codeTableLocks(Parse *pParse){
  int i;
  Vdbe *pVdbe;

  pVdbe = sqlite3GetVdbe(pParse);
  assert( pVdbe!=0 ); /* sqlite3GetVdbe cannot fail: VDBE already allocated */

  for(i=0; i<pParse->nTableLock; i++){
    TableLock *p = &pParse->aTableLock[i];
    int p1 = p->iDb;
    sqlite3VdbeAddOp4(pVdbe, OP_TableLock, p1, p->iTab, p->isWriteLock,
                      p->zLockName, P4_STATIC);
  }
}
#else
  #define codeTableLocks(x)
#endif

/*
** Return TRUE if the given yDbMask object is empty - if it contains no
** 1 bits.  This routine is used by the DbMaskAllZero() and DbMaskNotZero()
** macros when SQLITE_MAX_ATTACHED is greater than 30.
*/
#if SQLITE_MAX_ATTACHED>30
int sqlite3DbMaskAllZero(yDbMask m){
  int i;
  for(i=0; i<sizeof(yDbMask); i++) if( m[i] ) return 0;
  return 1;
}
#endif

/*
** This routine is called after a single SQL statement has been
** parsed and a VDBE program to execute that statement has been
** prepared.  This routine puts the finishing touches on the
** VDBE program and resets the pParse structure for the next
** parse.
**
** Note that if an error occurred, it might be the case that
** no VDBE code was generated.
*/
void sqlite3FinishCoding(Parse *pParse){
  sqlite3 *db;
  Vdbe *v;

  assert( pParse->pToplevel==0 );
  db = pParse->db;
  if( pParse->nested ) return;
  if( db->mallocFailed || pParse->nErr ){
    if( pParse->rc==SQLITE_OK ) pParse->rc = SQLITE_ERROR;
    return;
  }

  /* Begin by generating some termination code at the end of the
  ** vdbe program
  */
  v = sqlite3GetVdbe(pParse);
  assert( !pParse->isMultiWrite
       || sqlite3VdbeAssertMayAbort(v, pParse->mayAbort));
  if( v ){
    sqlite3VdbeAddOp0(v, OP_Halt);

#if SQLITE_USER_AUTHENTICATION
    if( pParse->nTableLock>0 && db->init.busy==0 ){
      sqlite3UserAuthInit(db);
      if( db->auth.authLevel<UAUTH_User ){
        sqlite3ErrorMsg(pParse, "user not authenticated");
        pParse->rc = SQLITE_AUTH_USER;
        return;
      }
    }
#endif

    /* The cookie mask contains one bit for each database file open.
    ** (Bit 0 is for main, bit 1 is for temp, and so forth.)  Bits are
    ** set for each database that is used.  Generate code to start a
    ** transaction on each used database and to verify the schema cookie
    ** on each used database.
    */
    if( db->mallocFailed==0
     && (DbMaskNonZero(pParse->cookieMask) || pParse->pConstExpr)
    ){
      int iDb, i;
      assert( sqlite3VdbeGetOp(v, 0)->opcode==OP_Init );
      sqlite3VdbeJumpHere(v, 0);
      for(iDb=0; iDb<db->nDb; iDb++){
        Schema *pSchema;
        if( DbMaskTest(pParse->cookieMask, iDb)==0 ) continue;
        sqlite3VdbeUsesBtree(v, iDb);
        pSchema = db->aDb[iDb].pSchema;
        sqlite3VdbeAddOp4Int(v,
          OP_Transaction,                    /* Opcode */
          iDb,                               /* P1 */
          DbMaskTest(pParse->writeMask,iDb), /* P2 */
          pSchema->schema_cookie,            /* P3 */
          pSchema->iGeneration               /* P4 */
        );
        if( db->init.busy==0 ) sqlite3VdbeChangeP5(v, 1);
        VdbeComment((v,
              "usesStmtJournal=%d", pParse->mayAbort && pParse->isMultiWrite));
      }
#ifndef SQLITE_OMIT_VIRTUALTABLE
      for(i=0; i<pParse->nVtabLock; i++){
        char *vtab = (char *)sqlite3GetVTable(db, pParse->apVtabLock[i]);
        sqlite3VdbeAddOp4(v, OP_VBegin, 0, 0, 0, vtab, P4_VTAB);
      }
      pParse->nVtabLock = 0;
#endif

      /* Once all the cookies have been verified and transactions opened,
      ** obtain the required table-locks. This is a no-op unless the
      ** shared-cache feature is enabled.
      */
      codeTableLocks(pParse);

      /* Initialize any AUTOINCREMENT data structures required.
      */
      sqlite3AutoincrementBegin(pParse);

      /* Code constant expressions that where factored out of inner loops */
      if( pParse->pConstExpr ){
        ExprList *pEL = pParse->pConstExpr;
        pParse->okConstFactor = 0;
        for(i=0; i<pEL->nExpr; i++){
          sqlite3ExprCode(pParse, pEL->a[i].pExpr, pEL->a[i].u.iConstExprReg);
        }
      }

      /* Finally, jump back to the beginning of the executable code. */
      sqlite3VdbeGoto(v, 1);
    }
  }


  /* Get the VDBE program ready for execution
  */
  if( v && pParse->nErr==0 && !db->mallocFailed ){
    /* A minimum of one cursor is required if autoincrement is used
    *  See ticket [a696379c1f08866] */
    assert( pParse->pAinc==0 || pParse->nTab>0 );
    sqlite3VdbeMakeReady(v, pParse);
    pParse->rc = SQLITE_DONE;
  }else{
    pParse->rc = SQLITE_ERROR;
  }
}

/*
** Run the parser and code generator recursively in order to generate
** code for the SQL statement given onto the end of the pParse context
** currently under construction.  When the parser is run recursively
** this way, the final OP_Halt is not appended and other initialization
** and finalization steps are omitted because those are handling by the
** outermost parser.
**
** Not everything is nestable.  This facility is designed to permit
** INSERT, UPDATE, and DELETE operations against SQLITE_MASTER.  Use
** care if you decide to try to use this routine for some other purposes.
*/
void sqlite3NestedParse(Parse *pParse, const char *zFormat, ...){
  va_list ap;
  char *zSql;
  char *zErrMsg = 0;
  sqlite3 *db = pParse->db;
  char saveBuf[PARSE_TAIL_SZ];

  if( pParse->nErr ) return;
  assert( pParse->nested<10 );  /* Nesting should only be of limited depth */
  va_start(ap, zFormat);
  zSql = sqlite3VMPrintf(db, zFormat, ap);
  va_end(ap);
  if( zSql==0 ){
    /* This can result either from an OOM or because the formatted string
    ** exceeds SQLITE_LIMIT_LENGTH.  In the latter case, we need to set
    ** an error */
    if( !db->mallocFailed ) pParse->rc = SQLITE_TOOBIG;
    pParse->nErr++;
    return;
  }
  pParse->nested++;
  memcpy(saveBuf, PARSE_TAIL(pParse), PARSE_TAIL_SZ);
  memset(PARSE_TAIL(pParse), 0, PARSE_TAIL_SZ);
  sqlite3RunParser(pParse, zSql, &zErrMsg);
  sqlite3DbFree(db, zErrMsg);
  sqlite3DbFree(db, zSql);
  memcpy(PARSE_TAIL(pParse), saveBuf, PARSE_TAIL_SZ);
  pParse->nested--;
}

#if SQLITE_USER_AUTHENTICATION
/*
** Return TRUE if zTable is the name of the system table that stores the
** list of users and their access credentials.
*/
int sqlite3UserAuthTable(const char *zTable){
  return sqlite3_stricmp(zTable, "sqlite_user")==0;
}
#endif

/*
** Locate the in-memory structure that describes a particular database
** table given the name of that table and (optionally) the name of the
** database containing the table.  Return NULL if not found.
**
** If zDatabase is 0, all databases are searched for the table and the
** first matching table is returned.  (No checking for duplicate table
** names is done.)  The search order is TEMP first, then MAIN, then any
** auxiliary databases added using the ATTACH command.
**
** See also sqlite3LocateTable().
*/
Table *sqlite3FindTable(sqlite3 *db, const char *zName, const char *zDatabase){
  Table *p = 0;
  int i;

  /* All mutexes are required for schema access.  Make sure we hold them. */
  assert( zDatabase!=0 || sqlite3BtreeHoldsAllMutexes(db) );
#if SQLITE_USER_AUTHENTICATION
  /* Only the admin user is allowed to know that the sqlite_user table
  ** exists */
  if( db->auth.authLevel<UAUTH_Admin && sqlite3UserAuthTable(zName)!=0 ){
    return 0;
  }
#endif
  while(1){
    for(i=OMIT_TEMPDB; i<db->nDb; i++){
      int j = (i<2) ? i^1 : i;   /* Search TEMP before MAIN */
      if( zDatabase==0 || sqlite3StrICmp(zDatabase, db->aDb[j].zDbSName)==0 ){
        assert( sqlite3SchemaMutexHeld(db, j, 0) );
        p = sqlite3HashFind(&db->aDb[j].pSchema->tblHash, zName);
        if( p ) return p;
      }
    }
    /* Not found.  If the name we were looking for was temp.sqlite_master
    ** then change the name to sqlite_temp_master and try again. */
    if( sqlite3StrICmp(zName, MASTER_NAME)!=0 ) break;
    if( sqlite3_stricmp(zDatabase, db->aDb[1].zDbSName)!=0 ) break;
    zName = TEMP_MASTER_NAME;
  }
  return 0;
}

/*
** Locate the in-memory structure that describes a particular database
** table given the name of that table and (optionally) the name of the
** database containing the table.  Return NULL if not found.  Also leave an
** error message in pParse->zErrMsg.
**
** The difference between this routine and sqlite3FindTable() is that this
** routine leaves an error message in pParse->zErrMsg where
** sqlite3FindTable() does not.
*/
Table *sqlite3LocateTable(
  Parse *pParse,         /* context in which to report errors */
  u32 flags,             /* LOCATE_VIEW or LOCATE_NOERR */
  const char *zName,     /* Name of the table we are looking for */
  const char *zDbase     /* Name of the database.  Might be NULL */
){
  Table *p;
  sqlite3 *db = pParse->db;

  /* Read the database schema. If an error occurs, leave an error message
  ** and code in pParse and return NULL. */
  if( (db->mDbFlags & DBFLAG_SchemaKnownOk)==0
   && SQLITE_OK!=sqlite3ReadSchema(pParse)
  ){
    return 0;
  }

  p = sqlite3FindTable(db, zName, zDbase);
  if( p==0 ){
#ifndef SQLITE_OMIT_VIRTUALTABLE
    /* If zName is the not the name of a table in the schema created using
    ** CREATE, then check to see if it is the name of an virtual table that
    ** can be an eponymous virtual table. */
    if( pParse->disableVtab==0 ){
      Module *pMod = (Module*)sqlite3HashFind(&db->aModule, zName);
      if( pMod==0 && sqlite3_strnicmp(zName, "pragma_", 7)==0 ){
        pMod = sqlite3PragmaVtabRegister(db, zName);
      }
      if( pMod && sqlite3VtabEponymousTableInit(pParse, pMod) ){
        return pMod->pEpoTab;
      }
    }
#endif
    if( flags & LOCATE_NOERR ) return 0;
    pParse->checkSchema = 1;
  }else if( IsVirtual(p) && pParse->disableVtab ){
    p = 0;
  }

  if( p==0 ){
    const char *zMsg = flags & LOCATE_VIEW ? "no such view" : "no such table";
    if( zDbase ){
      sqlite3ErrorMsg(pParse, "%s: %s.%s", zMsg, zDbase, zName);
    }else{
      sqlite3ErrorMsg(pParse, "%s: %s", zMsg, zName);
    }
  }

  return p;
}

/*
** Locate the table identified by *p.
**
** This is a wrapper around sqlite3LocateTable(). The difference between
** sqlite3LocateTable() and this function is that this function restricts
** the search to schema (p->pSchema) if it is not NULL. p->pSchema may be
** non-NULL if it is part of a view or trigger program definition. See
** sqlite3FixSrcList() for details.
*/
Table *sqlite3LocateTableItem(
  Parse *pParse,
  u32 flags,
  struct SrcList_item *p
){
  const char *zDb;
  assert( p->pSchema==0 || p->zDatabase==0 );
  if( p->pSchema ){
    int iDb = sqlite3SchemaToIndex(pParse->db, p->pSchema);
    zDb = pParse->db->aDb[iDb].zDbSName;
  }else{
    zDb = p->zDatabase;
  }
  return sqlite3LocateTable(pParse, flags, p->zName, zDb);
}

/*
** Locate the in-memory structure that describes
** a particular index given the name of that index
** and the name of the database that contains the index.
** Return NULL if not found.
**
** If zDatabase is 0, all databases are searched for the
** table and the first matching index is returned.  (No checking
** for duplicate index names is done.)  The search order is
** TEMP first, then MAIN, then any auxiliary databases added
** using the ATTACH command.
*/
Index *sqlite3FindIndex(sqlite3 *db, const char *zName, const char *zDb){
  Index *p = 0;
  int i;
  /* All mutexes are required for schema access.  Make sure we hold them. */
  assert( zDb!=0 || sqlite3BtreeHoldsAllMutexes(db) );
  for(i=OMIT_TEMPDB; i<db->nDb; i++){
    int j = (i<2) ? i^1 : i;  /* Search TEMP before MAIN */
    Schema *pSchema = db->aDb[j].pSchema;
    assert( pSchema );
    if( zDb && sqlite3StrICmp(zDb, db->aDb[j].zDbSName) ) continue;
    assert( sqlite3SchemaMutexHeld(db, j, 0) );
    p = sqlite3HashFind(&pSchema->idxHash, zName);
    if( p ) break;
  }
  return p;
}

/*
** Reclaim the memory used by an index
*/
void sqlite3FreeIndex(sqlite3 *db, Index *p){
#ifndef SQLITE_OMIT_ANALYZE
  sqlite3DeleteIndexSamples(db, p);
#endif
  sqlite3ExprDelete(db, p->pPartIdxWhere);
  sqlite3ExprListDelete(db, p->aColExpr);
  sqlite3DbFree(db, p->zColAff);
  if( p->isResized ) sqlite3DbFree(db, (void *)p->azColl);
#ifdef SQLITE_ENABLE_STAT4
  sqlite3_free(p->aiRowEst);
#endif
  sqlite3DbFree(db, p);
}

/*
** For the index called zIdxName which is found in the database iDb,
** unlike that index from its Table then remove the index from
** the index hash table and free all memory structures associated
** with the index.
*/
void sqlite3UnlinkAndDeleteIndex(sqlite3 *db, int iDb, const char *zIdxName){
  Index *pIndex;
  Hash *pHash;

  assert( sqlite3SchemaMutexHeld(db, iDb, 0) );
  pHash = &db->aDb[iDb].pSchema->idxHash;
  pIndex = sqlite3HashInsert(pHash, zIdxName, 0);
  if( ALWAYS(pIndex) ){
    if( pIndex->pTable->pIndex==pIndex ){
      pIndex->pTable->pIndex = pIndex->pNext;
    }else{
      Index *p;
      /* Justification of ALWAYS();  The index must be on the list of
      ** indices. */
      p = pIndex->pTable->pIndex;
      while( ALWAYS(p) && p->pNext!=pIndex ){ p = p->pNext; }
      if( ALWAYS(p && p->pNext==pIndex) ){
        p->pNext = pIndex->pNext;
      }
    }
    sqlite3FreeIndex(db, pIndex);
  }
  db->mDbFlags |= DBFLAG_SchemaChange;
}

/*
** Look through the list of open database files in db->aDb[] and if
** any have been closed, remove them from the list.  Reallocate the
** db->aDb[] structure to a smaller size, if possible.
**
** Entry 0 (the "main" database) and entry 1 (the "temp" database)
** are never candidates for being collapsed.
*/
void sqlite3CollapseDatabaseArray(sqlite3 *db){
  int i, j;
  for(i=j=2; i<db->nDb; i++){
    struct Db *pDb = &db->aDb[i];
    if( pDb->pBt==0 ){
      sqlite3DbFree(db, pDb->zDbSName);
      pDb->zDbSName = 0;
      continue;
    }
    if( j<i ){
      db->aDb[j] = db->aDb[i];
    }
    j++;
  }
  db->nDb = j;
  if( db->nDb<=2 && db->aDb!=db->aDbStatic ){
    memcpy(db->aDbStatic, db->aDb, 2*sizeof(db->aDb[0]));
    sqlite3DbFree(db, db->aDb);
    db->aDb = db->aDbStatic;
  }
}

/*
** Reset the schema for the database at index iDb.  Also reset the
** TEMP schema.  The reset is deferred if db->nSchemaLock is not zero.
** Deferred resets may be run by calling with iDb<0.
*/
void sqlite3ResetOneSchema(sqlite3 *db, int iDb){
  int i;
  assert( iDb<db->nDb );

  if( iDb>=0 ){
    assert( sqlite3SchemaMutexHeld(db, iDb, 0) );
    DbSetProperty(db, iDb, DB_ResetWanted);
    DbSetProperty(db, 1, DB_ResetWanted);
    db->mDbFlags &= ~DBFLAG_SchemaKnownOk;
  }

  if( db->nSchemaLock==0 ){
    for(i=0; i<db->nDb; i++){
      if( DbHasProperty(db, i, DB_ResetWanted) ){
        sqlite3SchemaClear(db->aDb[i].pSchema);
      }
    }
  }
}

/*
** Erase all schema information from all attached databases (including
** "main" and "temp") for a single database connection.
*/
void sqlite3ResetAllSchemasOfConnection(sqlite3 *db){
  int i;
  sqlite3BtreeEnterAll(db);
  for(i=0; i<db->nDb; i++){
    Db *pDb = &db->aDb[i];
    if( pDb->pSchema ){
      if( db->nSchemaLock==0 ){
        sqlite3SchemaClear(pDb->pSchema);
      }else{
        DbSetProperty(db, i, DB_ResetWanted);
      }
    }
  }
  db->mDbFlags &= ~(DBFLAG_SchemaChange|DBFLAG_SchemaKnownOk);
  sqlite3VtabUnlockList(db);
  sqlite3BtreeLeaveAll(db);
  if( db->nSchemaLock==0 ){
    sqlite3CollapseDatabaseArray(db);
  }
}

/*
** This routine is called when a commit occurs.
*/
void sqlite3CommitInternalChanges(sqlite3 *db){
  db->mDbFlags &= ~DBFLAG_SchemaChange;
}

/*
** Delete memory allocated for the column names of a table or view (the
** Table.aCol[] array).
*/
void sqlite3DeleteColumnNames(sqlite3 *db, Table *pTable){
  int i;
  Column *pCol;
  assert( pTable!=0 );
  if( (pCol = pTable->aCol)!=0 ){
    for(i=0; i<pTable->nCol; i++, pCol++){
      sqlite3DbFree(db, pCol->zName);
      sqlite3ExprDelete(db, pCol->pDflt);
      sqlite3DbFree(db, pCol->zColl);
    }
    sqlite3DbFree(db, pTable->aCol);
  }
}

/*
** Remove the memory data structures associated with the given
** Table.  No changes are made to disk by this routine.
**
** This routine just deletes the data structure.  It does not unlink
** the table data structure from the hash table.  But it does destroy
** memory structures of the indices and foreign keys associated with
** the table.
**
** The db parameter is optional.  It is needed if the Table object
** contains lookaside memory.  (Table objects in the schema do not use
** lookaside memory, but some ephemeral Table objects do.)  Or the
** db parameter can be used with db->pnBytesFreed to measure the memory
** used by the Table object.
*/
static void SQLITE_NOINLINE deleteTable(sqlite3 *db, Table *pTable){
  Index *pIndex, *pNext;

#ifdef SQLITE_DEBUG
  /* Record the number of outstanding lookaside allocations in schema Tables
  ** prior to doing any free() operations. Since schema Tables do not use
  ** lookaside, this number should not change.
  **
  ** If malloc has already failed, it may be that it failed while allocating
  ** a Table object that was going to be marked ephemeral. So do not check
  ** that no lookaside memory is used in this case either. */
  int nLookaside = 0;
  if( db && !db->mallocFailed && (pTable->tabFlags & TF_Ephemeral)==0 ){
    nLookaside = sqlite3LookasideUsed(db, 0);
  }
#endif

  /* Delete all indices associated with this table. */
  for(pIndex = pTable->pIndex; pIndex; pIndex=pNext){
    pNext = pIndex->pNext;
    assert( pIndex->pSchema==pTable->pSchema
         || (IsVirtual(pTable) && pIndex->idxType!=SQLITE_IDXTYPE_APPDEF) );
    if( (db==0 || db->pnBytesFreed==0) && !IsVirtual(pTable) ){
      char *zName = pIndex->zName;
      TESTONLY ( Index *pOld = ) sqlite3HashInsert(
         &pIndex->pSchema->idxHash, zName, 0
      );
      assert( db==0 || sqlite3SchemaMutexHeld(db, 0, pIndex->pSchema) );
      assert( pOld==pIndex || pOld==0 );
    }
    sqlite3FreeIndex(db, pIndex);
  }

  /* Delete any foreign keys attached to this table. */
  sqlite3FkDelete(db, pTable);

  /* Delete the Table structure itself.
  */
  sqlite3DeleteColumnNames(db, pTable);
  sqlite3DbFree(db, pTable->zName);
  sqlite3DbFree(db, pTable->zColAff);
  sqlite3SelectDelete(db, pTable->pSelect);
  sqlite3ExprListDelete(db, pTable->pCheck);
#ifndef SQLITE_OMIT_VIRTUALTABLE
  sqlite3VtabClear(db, pTable);
#endif
  sqlite3DbFree(db, pTable);

  /* Verify that no lookaside memory was used by schema tables */
  assert( nLookaside==0 || nLookaside==sqlite3LookasideUsed(db,0) );
}
void sqlite3DeleteTable(sqlite3 *db, Table *pTable){
  /* Do not delete the table until the reference count reaches zero. */
  if( !pTable ) return;
  if( ((!db || db->pnBytesFreed==0) && (--pTable->nTabRef)>0) ) return;
  deleteTable(db, pTable);
}


/*
** Unlink the given table from the hash tables and the delete the
** table structure with all its indices and foreign keys.
*/
void sqlite3UnlinkAndDeleteTable(sqlite3 *db, int iDb, const char *zTabName){
  Table *p;
  Db *pDb;

  assert( db!=0 );
  assert( iDb>=0 && iDb<db->nDb );
  assert( zTabName );
  assert( sqlite3SchemaMutexHeld(db, iDb, 0) );
  testcase( zTabName[0]==0 );  /* Zero-length table names are allowed */
  pDb = &db->aDb[iDb];
  p = sqlite3HashInsert(&pDb->pSchema->tblHash, zTabName, 0);
  sqlite3DeleteTable(db, p);
  db->mDbFlags |= DBFLAG_SchemaChange;
}

/*
** Given a token, return a string that consists of the text of that
** token.  Space to hold the returned string
** is obtained from sqliteMalloc() and must be freed by the calling
** function.
**
** Any quotation marks (ex:  "name", 'name', [name], or `name`) that
** surround the body of the token are removed.
**
** Tokens are often just pointers into the original SQL text and so
** are not \000 terminated and are not persistent.  The returned string
** is \000 terminated and is persistent.
*/
char *sqlite3NameFromToken(sqlite3 *db, Token *pName){
  char *zName;
  if( pName ){
    zName = sqlite3DbStrNDup(db, (char*)pName->z, pName->n);
    sqlite3Dequote(zName);
  }else{
    zName = 0;
  }
  return zName;
}

/*
** Open the sqlite_master table stored in database number iDb for
** writing. The table is opened using cursor 0.
*/
void sqlite3OpenMasterTable(Parse *p, int iDb){
  Vdbe *v = sqlite3GetVdbe(p);
  sqlite3TableLock(p, iDb, MASTER_ROOT, 1, MASTER_NAME);
  sqlite3VdbeAddOp4Int(v, OP_OpenWrite, 0, MASTER_ROOT, iDb, 5);
  if( p->nTab==0 ){
    p->nTab = 1;
  }
}

/*
** Parameter zName points to a nul-terminated buffer containing the name
** of a database ("main", "temp" or the name of an attached db). This
** function returns the index of the named database in db->aDb[], or
** -1 if the named db cannot be found.
*/
int sqlite3FindDbName(sqlite3 *db, const char *zName){
  int i = -1;         /* Database number */
  if( zName ){
    Db *pDb;
    for(i=(db->nDb-1), pDb=&db->aDb[i]; i>=0; i--, pDb--){
      if( 0==sqlite3_stricmp(pDb->zDbSName, zName) ) break;
      /* "main" is always an acceptable alias for the primary database
      ** even if it has been renamed using SQLITE_DBCONFIG_MAINDBNAME. */
      if( i==0 && 0==sqlite3_stricmp("main", zName) ) break;
    }
  }
  return i;
}

/*
** The token *pName contains the name of a database (either "main" or
** "temp" or the name of an attached db). This routine returns the
** index of the named database in db->aDb[], or -1 if the named db
** does not exist.
*/
int sqlite3FindDb(sqlite3 *db, Token *pName){
  int i;                               /* Database number */
  char *zName;                         /* Name we are searching for */
  zName = sqlite3NameFromToken(db, pName);
  i = sqlite3FindDbName(db, zName);
  sqlite3DbFree(db, zName);
  return i;
}

/* The table or view or trigger name is passed to this routine via tokens
** pName1 and pName2. If the table name was fully qualified, for example:
**
** CREATE TABLE xxx.yyy (...);
**
** Then pName1 is set to "xxx" and pName2 "yyy". On the other hand if
** the table name is not fully qualified, i.e.:
**
** CREATE TABLE yyy(...);
**
** Then pName1 is set to "yyy" and pName2 is "".
**
** This routine sets the *ppUnqual pointer to point at the token (pName1 or
** pName2) that stores the unqualified table name.  The index of the
** database "xxx" is returned.
*/
int sqlite3TwoPartName(
  Parse *pParse,      /* Parsing and code generating context */
  Token *pName1,      /* The "xxx" in the name "xxx.yyy" or "xxx" */
  Token *pName2,      /* The "yyy" in the name "xxx.yyy" */
  Token **pUnqual     /* Write the unqualified object name here */
){
  int iDb;                    /* Database holding the object */
  sqlite3 *db = pParse->db;

  assert( pName2!=0 );
  if( pName2->n>0 ){
    if( db->init.busy ) {
      sqlite3ErrorMsg(pParse, "corrupt database");
      return -1;
    }
    *pUnqual = pName2;
    iDb = sqlite3FindDb(db, pName1);
    if( iDb<0 ){
      sqlite3ErrorMsg(pParse, "unknown database %T", pName1);
      return -1;
    }
  }else{
    assert( db->init.iDb==0 || db->init.busy || IN_RENAME_OBJECT
             || (db->mDbFlags & DBFLAG_Vacuum)!=0);
    iDb = db->init.iDb;
    *pUnqual = pName1;
  }
  return iDb;
}

/*
** True if PRAGMA writable_schema is ON
*/
int sqlite3WritableSchema(sqlite3 *db){
  testcase( (db->flags&(SQLITE_WriteSchema|SQLITE_Defensive))==0 );
  testcase( (db->flags&(SQLITE_WriteSchema|SQLITE_Defensive))==
               SQLITE_WriteSchema );
  testcase( (db->flags&(SQLITE_WriteSchema|SQLITE_Defensive))==
               SQLITE_Defensive );
  testcase( (db->flags&(SQLITE_WriteSchema|SQLITE_Defensive))==
               (SQLITE_WriteSchema|SQLITE_Defensive) );
  return (db->flags&(SQLITE_WriteSchema|SQLITE_Defensive))==SQLITE_WriteSchema;
}

/*
** This routine is used to check if the UTF-8 string zName is a legal
** unqualified name for a new schema object (table, index, view or
** trigger). All names are legal except those that begin with the string
** "sqlite_" (in upper, lower or mixed case). This portion of the namespace
** is reserved for internal use.
**
** When parsing the sqlite_master table, this routine also checks to
** make sure the "type", "name", and "tbl_name" columns are consistent
** with the SQL.
*/
int sqlite3CheckObjectName(
  Parse *pParse,            /* Parsing context */
  const char *zName,        /* Name of the object to check */
  const char *zType,        /* Type of this object */
  const char *zTblName      /* Parent table name for triggers and indexes */
){
  sqlite3 *db = pParse->db;
  if( sqlite3WritableSchema(db) || db->init.imposterTable ){
    /* Skip these error checks for writable_schema=ON */
    return SQLITE_OK;
  }
  if( db->init.busy ){
    if( sqlite3_stricmp(zType, db->init.azInit[0])
     || sqlite3_stricmp(zName, db->init.azInit[1])
     || sqlite3_stricmp(zTblName, db->init.azInit[2])
    ){
      if( sqlite3Config.bExtraSchemaChecks ){
        sqlite3ErrorMsg(pParse, ""); /* corruptSchema() will supply the error */
        return SQLITE_ERROR;
      }
    }
  }else{
    if( pParse->nested==0
     && 0==sqlite3StrNICmp(zName, "sqlite_", 7)
    ){
      sqlite3ErrorMsg(pParse, "object name reserved for internal use: %s",
                      zName);
      return SQLITE_ERROR;
    }
  }
  return SQLITE_OK;
}

/*
** Return the PRIMARY KEY index of a table
*/
Index *sqlite3PrimaryKeyIndex(Table *pTab){
  Index *p;
  for(p=pTab->pIndex; p && !IsPrimaryKeyIndex(p); p=p->pNext){}
  return p;
}

/*
** Return the column of index pIdx that corresponds to table
** column iCol.  Return -1 if not found.
*/
i16 sqlite3ColumnOfIndex(Index *pIdx, i16 iCol){
  int i;
  for(i=0; i<pIdx->nColumn; i++){
    if( iCol==pIdx->aiColumn[i] ) return i;
  }
  return -1;
}

/*
** Begin constructing a new table representation in memory.  This is
** the first of several action routines that get called in response
** to a CREATE TABLE statement.  In particular, this routine is called
** after seeing tokens "CREATE" and "TABLE" and the table name. The isTemp
** flag is true if the table should be stored in the auxiliary database
** file instead of in the main database file.  This is normally the case
** when the "TEMP" or "TEMPORARY" keyword occurs in between
** CREATE and TABLE.
**
** The new table record is initialized and put in pParse->pNewTable.
** As more of the CREATE TABLE statement is parsed, additional action
** routines will be called to add more information to this record.
** At the end of the CREATE TABLE statement, the sqlite3EndTable() routine
** is called to complete the construction of the new table record.
*/
void sqlite3StartTable(
  Parse *pParse,   /* Parser context */
  Token *pName1,   /* First part of the name of the table or view */
  Token *pName2,   /* Second part of the name of the table or view */
  int isTemp,      /* True if this is a TEMP table */
  int isView,      /* True if this is a VIEW */
  int isVirtual,   /* True if this is a VIRTUAL table */
  int noErr        /* Do nothing if table already exists */
){
  Table *pTable;
  char *zName = 0; /* The name of the new table */
  sqlite3 *db = pParse->db;
  Vdbe *v;
  int iDb;         /* Database number to create the table in */
  Token *pName;    /* Unqualified name of the table to create */

  if( db->init.busy && db->init.newTnum==1 ){
    /* Special case:  Parsing the sqlite_master or sqlite_temp_master schema */
    iDb = db->init.iDb;
    zName = sqlite3DbStrDup(db, SCHEMA_TABLE(iDb));
    pName = pName1;
  }else{
    /* The common case */
    iDb = sqlite3TwoPartName(pParse, pName1, pName2, &pName);
    if( iDb<0 ) return;
    if( !OMIT_TEMPDB && isTemp && pName2->n>0 && iDb!=1 ){
      /* If creating a temp table, the name may not be qualified. Unless
      ** the database name is "temp" anyway.  */
      sqlite3ErrorMsg(pParse, "temporary table name must be unqualified");
      return;
    }
    if( !OMIT_TEMPDB && isTemp ) iDb = 1;
    zName = sqlite3NameFromToken(db, pName);
    if( IN_RENAME_OBJECT ){
      sqlite3RenameTokenMap(pParse, (void*)zName, pName);
    }
  }
  pParse->sNameToken = *pName;
  if( zName==0 ) return;
  if( sqlite3CheckObjectName(pParse, zName, isView?"view":"table", zName) ){
    goto begin_table_error;
  }
  if( db->init.iDb==1 ) isTemp = 1;
#ifndef SQLITE_OMIT_AUTHORIZATION
  assert( isTemp==0 || isTemp==1 );
  assert( isView==0 || isView==1 );
  {
    static const u8 aCode[] = {
       SQLITE_CREATE_TABLE,
       SQLITE_CREATE_TEMP_TABLE,
       SQLITE_CREATE_VIEW,
       SQLITE_CREATE_TEMP_VIEW
    };
    char *zDb = db->aDb[iDb].zDbSName;
    if( sqlite3AuthCheck(pParse, SQLITE_INSERT, SCHEMA_TABLE(isTemp), 0, zDb) ){
      goto begin_table_error;
    }
    if( !isVirtual && sqlite3AuthCheck(pParse, (int)aCode[isTemp+2*isView],
                                       zName, 0, zDb) ){
      goto begin_table_error;
    }
  }
#endif

  /* Make sure the new table name does not collide with an existing
  ** index or table name in the same database.  Issue an error message if
  ** it does. The exception is if the statement being parsed was passed
  ** to an sqlite3_declare_vtab() call. In that case only the column names
  ** and types will be used, so there is no need to test for namespace
  ** collisions.
  */
  if( !IN_SPECIAL_PARSE ){
    char *zDb = db->aDb[iDb].zDbSName;
    if( SQLITE_OK!=sqlite3ReadSchema(pParse) ){
      goto begin_table_error;
    }
    pTable = sqlite3FindTable(db, zName, zDb);
    if( pTable ){
      if( !noErr ){
        sqlite3ErrorMsg(pParse, "table %T already exists", pName);
      }else{
        assert( !db->init.busy || CORRUPT_DB );
        sqlite3CodeVerifySchema(pParse, iDb);
      }
      goto begin_table_error;
    }
    if( sqlite3FindIndex(db, zName, zDb)!=0 ){
      sqlite3ErrorMsg(pParse, "there is already an index named %s", zName);
      goto begin_table_error;
    }
  }

  pTable = sqlite3DbMallocZero(db, sizeof(Table));
  if( pTable==0 ){
    assert( db->mallocFailed );
    pParse->rc = SQLITE_NOMEM_BKPT;
    pParse->nErr++;
    goto begin_table_error;
  }
  pTable->zName = zName;
  pTable->iPKey = -1;
  pTable->pSchema = db->aDb[iDb].pSchema;
  pTable->nTabRef = 1;
#ifdef SQLITE_DEFAULT_ROWEST
  pTable->nRowLogEst = sqlite3LogEst(SQLITE_DEFAULT_ROWEST);
#else
  pTable->nRowLogEst = 200; assert( 200==sqlite3LogEst(1048576) );
#endif
  assert( pParse->pNewTable==0 );
  pParse->pNewTable = pTable;

  /* If this is the magic sqlite_sequence table used by autoincrement,
  ** then record a pointer to this table in the main database structure
  ** so that INSERT can find the table easily.
  */
#ifndef SQLITE_OMIT_AUTOINCREMENT
  if( !pParse->nested && strcmp(zName, "sqlite_sequence")==0 ){
    assert( sqlite3SchemaMutexHeld(db, iDb, 0) );
    pTable->pSchema->pSeqTab = pTable;
  }
#endif

  /* Begin generating the code that will insert the table record into
  ** the SQLITE_MASTER table.  Note in particular that we must go ahead
  ** and allocate the record number for the table entry now.  Before any
  ** PRIMARY KEY or UNIQUE keywords are parsed.  Those keywords will cause
  ** indices to be created and the table record must come before the
  ** indices.  Hence, the record number for the table must be allocated
  ** now.
  */
  if( !db->init.busy && (v = sqlite3GetVdbe(pParse))!=0 ){
    int addr1;
    int fileFormat;
    int reg1, reg2, reg3;
    /* nullRow[] is an OP_Record encoding of a row containing 5 NULLs */
    static const char nullRow[] = { 6, 0, 0, 0, 0, 0 };
    sqlite3BeginWriteOperation(pParse, 1, iDb);

#ifndef SQLITE_OMIT_VIRTUALTABLE
    if( isVirtual ){
      sqlite3VdbeAddOp0(v, OP_VBegin);
    }
#endif

    /* If the file format and encoding in the database have not been set,
    ** set them now.
    */
    reg1 = pParse->regRowid = ++pParse->nMem;
    reg2 = pParse->regRoot = ++pParse->nMem;
    reg3 = ++pParse->nMem;
    sqlite3VdbeAddOp3(v, OP_ReadCookie, iDb, reg3, BTREE_FILE_FORMAT);
    sqlite3VdbeUsesBtree(v, iDb);
    addr1 = sqlite3VdbeAddOp1(v, OP_If, reg3); VdbeCoverage(v);
    fileFormat = (db->flags & SQLITE_LegacyFileFmt)!=0 ?
                  1 : SQLITE_MAX_FILE_FORMAT;
    sqlite3VdbeAddOp3(v, OP_SetCookie, iDb, BTREE_FILE_FORMAT, fileFormat);
    sqlite3VdbeAddOp3(v, OP_SetCookie, iDb, BTREE_TEXT_ENCODING, ENC(db));
    sqlite3VdbeJumpHere(v, addr1);

    /* This just creates a place-holder record in the sqlite_master table.
    ** The record created does not contain anything yet.  It will be replaced
    ** by the real entry in code generated at sqlite3EndTable().
    **
    ** The rowid for the new entry is left in register pParse->regRowid.
    ** The root page number of the new table is left in reg pParse->regRoot.
    ** The rowid and root page number values are needed by the code that
    ** sqlite3EndTable will generate.
    */
#if !defined(SQLITE_OMIT_VIEW) || !defined(SQLITE_OMIT_VIRTUALTABLE)
    if( isView || isVirtual ){
      sqlite3VdbeAddOp2(v, OP_Integer, 0, reg2);
    }else
#endif
    {
      pParse->addrCrTab =
         sqlite3VdbeAddOp3(v, OP_CreateBtree, iDb, reg2, BTREE_INTKEY);
    }
    sqlite3OpenMasterTable(pParse, iDb);
    sqlite3VdbeAddOp2(v, OP_NewRowid, 0, reg1);
    sqlite3VdbeAddOp4(v, OP_Blob, 6, reg3, 0, nullRow, P4_STATIC);
    sqlite3VdbeAddOp3(v, OP_Insert, 0, reg3, reg1);
    sqlite3VdbeChangeP5(v, OPFLAG_APPEND);
    sqlite3VdbeAddOp0(v, OP_Close);
  }

  /* Normal (non-error) return. */
  return;

  /* If an error occurs, we jump here */
begin_table_error:
  sqlite3DbFree(db, zName);
  return;
}

/* Set properties of a table column based on the (magical)
** name of the column.
*/
#if SQLITE_ENABLE_HIDDEN_COLUMNS
void sqlite3ColumnPropertiesFromName(Table *pTab, Column *pCol){
  if( sqlite3_strnicmp(pCol->zName, "__hidden__", 10)==0 ){
    pCol->colFlags |= COLFLAG_HIDDEN;
  }else if( pTab && pCol!=pTab->aCol && (pCol[-1].colFlags & COLFLAG_HIDDEN) ){
    pTab->tabFlags |= TF_OOOHidden;
  }
}
#endif


/*
** Add a new column to the table currently being constructed.
**
** The parser calls this routine once for each column declaration
** in a CREATE TABLE statement.  sqlite3StartTable() gets called
** first to get things going.  Then this routine is called for each
** column.
*/
void sqlite3AddColumn(Parse *pParse, Token *pName, Token *pType){
  Table *p;
  int i;
  char *z;
  char *zType;
  Column *pCol;
  sqlite3 *db = pParse->db;
  if( (p = pParse->pNewTable)==0 ) return;
  if( p->nCol+1>db->aLimit[SQLITE_LIMIT_COLUMN] ){
    sqlite3ErrorMsg(pParse, "too many columns on %s", p->zName);
    return;
  }
  z = sqlite3DbMallocRaw(db, pName->n + pType->n + 2);
  if( z==0 ) return;
  if( IN_RENAME_OBJECT ) sqlite3RenameTokenMap(pParse, (void*)z, pName);
  memcpy(z, pName->z, pName->n);
  z[pName->n] = 0;
  sqlite3Dequote(z);
  for(i=0; i<p->nCol; i++){
    if( sqlite3_stricmp(z, p->aCol[i].zName)==0 ){
      sqlite3ErrorMsg(pParse, "duplicate column name: %s", z);
      sqlite3DbFree(db, z);
      return;
    }
  }
  if( (p->nCol & 0x7)==0 ){
    Column *aNew;
    aNew = sqlite3DbRealloc(db,p->aCol,(p->nCol+8)*sizeof(p->aCol[0]));
    if( aNew==0 ){
      sqlite3DbFree(db, z);
      return;
    }
    p->aCol = aNew;
  }
  pCol = &p->aCol[p->nCol];
  memset(pCol, 0, sizeof(p->aCol[0]));
  pCol->zName = z;
  sqlite3ColumnPropertiesFromName(p, pCol);

  if( pType->n==0 ){
    /* If there is no type specified, columns have the default affinity
    ** 'BLOB' with a default size of 4 bytes. */
    pCol->affinity = SQLITE_AFF_BLOB;
    pCol->szEst = 1;
#ifdef SQLITE_ENABLE_SORTER_REFERENCES
    if( 4>=sqlite3GlobalConfig.szSorterRef ){
      pCol->colFlags |= COLFLAG_SORTERREF;
    }
#endif
  }else{
    zType = z + sqlite3Strlen30(z) + 1;
    memcpy(zType, pType->z, pType->n);
    zType[pType->n] = 0;
    sqlite3Dequote(zType);
    pCol->affinity = sqlite3AffinityType(zType, pCol);
    pCol->colFlags |= COLFLAG_HASTYPE;
  }
  p->nCol++;
  pParse->constraintName.n = 0;
}

/*
** This routine is called by the parser while in the middle of
** parsing a CREATE TABLE statement.  A "NOT NULL" constraint has
** been seen on a column.  This routine sets the notNull flag on
** the column currently under construction.
*/
void sqlite3AddNotNull(Parse *pParse, int onError){
  Table *p;
  Column *pCol;
  p = pParse->pNewTable;
  if( p==0 || NEVER(p->nCol<1) ) return;
  pCol = &p->aCol[p->nCol-1];
  pCol->notNull = (u8)onError;
  p->tabFlags |= TF_HasNotNull;

  /* Set the uniqNotNull flag on any UNIQUE or PK indexes already created
  ** on this column.  */
  if( pCol->colFlags & COLFLAG_UNIQUE ){
    Index *pIdx;
    for(pIdx=p->pIndex; pIdx; pIdx=pIdx->pNext){
      assert( pIdx->nKeyCol==1 && pIdx->onError!=OE_None );
      if( pIdx->aiColumn[0]==p->nCol-1 ){
        pIdx->uniqNotNull = 1;
      }
    }
  }
}

/*
** Scan the column type name zType (length nType) and return the
** associated affinity type.
**
** This routine does a case-independent search of zType for the
** substrings in the following table. If one of the substrings is
** found, the corresponding affinity is returned. If zType contains
** more than one of the substrings, entries toward the top of
** the table take priority. For example, if zType is 'BLOBINT',
** SQLITE_AFF_INTEGER is returned.
**
** Substring     | Affinity
** --------------------------------
** 'INT'         | SQLITE_AFF_INTEGER
** 'CHAR'        | SQLITE_AFF_TEXT
** 'CLOB'        | SQLITE_AFF_TEXT
** 'TEXT'        | SQLITE_AFF_TEXT
** 'BLOB'        | SQLITE_AFF_BLOB
** 'REAL'        | SQLITE_AFF_REAL
** 'FLOA'        | SQLITE_AFF_REAL
** 'DOUB'        | SQLITE_AFF_REAL
**
** If none of the substrings in the above table are found,
** SQLITE_AFF_NUMERIC is returned.
*/
char sqlite3AffinityType(const char *zIn, Column *pCol){
  u32 h = 0;
  char aff = SQLITE_AFF_NUMERIC;
  const char *zChar = 0;

  assert( zIn!=0 );
  while( zIn[0] ){
    h = (h<<8) + sqlite3UpperToLower[(*zIn)&0xff];
    zIn++;
    if( h==(('c'<<24)+('h'<<16)+('a'<<8)+'r') ){             /* CHAR */
      aff = SQLITE_AFF_TEXT;
      zChar = zIn;
    }else if( h==(('c'<<24)+('l'<<16)+('o'<<8)+'b') ){       /* CLOB */
      aff = SQLITE_AFF_TEXT;
    }else if( h==(('t'<<24)+('e'<<16)+('x'<<8)+'t') ){       /* TEXT */
      aff = SQLITE_AFF_TEXT;
    }else if( h==(('b'<<24)+('l'<<16)+('o'<<8)+'b')          /* BLOB */
        && (aff==SQLITE_AFF_NUMERIC || aff==SQLITE_AFF_REAL) ){
      aff = SQLITE_AFF_BLOB;
      if( zIn[0]=='(' ) zChar = zIn;
#ifndef SQLITE_OMIT_FLOATING_POINT
    }else if( h==(('r'<<24)+('e'<<16)+('a'<<8)+'l')          /* REAL */
        && aff==SQLITE_AFF_NUMERIC ){
      aff = SQLITE_AFF_REAL;
    }else if( h==(('f'<<24)+('l'<<16)+('o'<<8)+'a')          /* FLOA */
        && aff==SQLITE_AFF_NUMERIC ){
      aff = SQLITE_AFF_REAL;
    }else if( h==(('d'<<24)+('o'<<16)+('u'<<8)+'b')          /* DOUB */
        && aff==SQLITE_AFF_NUMERIC ){
      aff = SQLITE_AFF_REAL;
#endif
    }else if( (h&0x00FFFFFF)==(('i'<<16)+('n'<<8)+'t') ){    /* INT */
      aff = SQLITE_AFF_INTEGER;
      break;
    }
  }

  /* If pCol is not NULL, store an estimate of the field size.  The
  ** estimate is scaled so that the size of an integer is 1.  */
  if( pCol ){
    int v = 0;   /* default size is approx 4 bytes */
    if( aff<SQLITE_AFF_NUMERIC ){
      if( zChar ){
        while( zChar[0] ){
          if( sqlite3Isdigit(zChar[0]) ){
            /* BLOB(k), VARCHAR(k), CHAR(k) -> r=(k/4+1) */
            sqlite3GetInt32(zChar, &v);
            break;
          }
          zChar++;
        }
      }else{
        v = 16;   /* BLOB, TEXT, CLOB -> r=5  (approx 20 bytes)*/
      }
    }
#ifdef SQLITE_ENABLE_SORTER_REFERENCES
    if( v>=sqlite3GlobalConfig.szSorterRef ){
      pCol->colFlags |= COLFLAG_SORTERREF;
    }
#endif
    v = v/4 + 1;
    if( v>255 ) v = 255;
    pCol->szEst = v;
  }
  return aff;
}

/*
** The expression is the default value for the most recently added column
** of the table currently under construction.
**
** Default value expressions must be constant.  Raise an exception if this
** is not the case.
**
** This routine is called by the parser while in the middle of
** parsing a CREATE TABLE statement.
*/
void sqlite3AddDefaultValue(
  Parse *pParse,           /* Parsing context */
  Expr *pExpr,             /* The parsed expression of the default value */
  const char *zStart,      /* Start of the default value text */
  const char *zEnd         /* First character past end of defaut value text */
){
  Table *p;
  Column *pCol;
  sqlite3 *db = pParse->db;
  p = pParse->pNewTable;
  if( p!=0 ){
    pCol = &(p->aCol[p->nCol-1]);
    if( !sqlite3ExprIsConstantOrFunction(pExpr, db->init.busy) ){
      sqlite3ErrorMsg(pParse, "default value of column [%s] is not constant",
          pCol->zName);
    }else{
      /* A copy of pExpr is used instead of the original, as pExpr contains
      ** tokens that point to volatile memory.
      */
      Expr x;
      sqlite3ExprDelete(db, pCol->pDflt);
      memset(&x, 0, sizeof(x));
      x.op = TK_SPAN;
      x.u.zToken = sqlite3DbSpanDup(db, zStart, zEnd);
      x.pLeft = pExpr;
      x.flags = EP_Skip;
      pCol->pDflt = sqlite3ExprDup(db, &x, EXPRDUP_REDUCE);
      sqlite3DbFree(db, x.u.zToken);
    }
  }
  if( IN_RENAME_OBJECT ){
    sqlite3RenameExprUnmap(pParse, pExpr);
  }
  sqlite3ExprDelete(db, pExpr);
}

/*
** Backwards Compatibility Hack:
**
** Historical versions of SQLite accepted strings as column names in
** indexes and PRIMARY KEY constraints and in UNIQUE constraints.  Example:
**
**     CREATE TABLE xyz(a,b,c,d,e,PRIMARY KEY('a'),UNIQUE('b','c' COLLATE trim)
**     CREATE INDEX abc ON xyz('c','d' DESC,'e' COLLATE nocase DESC);
**
** This is goofy.  But to preserve backwards compatibility we continue to
** accept it.  This routine does the necessary conversion.  It converts
** the expression given in its argument from a TK_STRING into a TK_ID
** if the expression is just a TK_STRING with an optional COLLATE clause.
** If the expression is anything other than TK_STRING, the expression is
** unchanged.
*/
static void sqlite3StringToId(Expr *p){
  if( p->op==TK_STRING ){
    p->op = TK_ID;
  }else if( p->op==TK_COLLATE && p->pLeft->op==TK_STRING ){
    p->pLeft->op = TK_ID;
  }
}

/*
** Designate the PRIMARY KEY for the table.  pList is a list of names
** of columns that form the primary key.  If pList is NULL, then the
** most recently added column of the table is the primary key.
**
** A table can have at most one primary key.  If the table already has
** a primary key (and this is the second primary key) then create an
** error.
**
** If the PRIMARY KEY is on a single column whose datatype is INTEGER,
** then we will try to use that column as the rowid.  Set the Table.iPKey
** field of the table under construction to be the index of the
** INTEGER PRIMARY KEY column.  Table.iPKey is set to -1 if there is
** no INTEGER PRIMARY KEY.
**
** If the key is not an INTEGER PRIMARY KEY, then create a unique
** index for the key.  No index is created for INTEGER PRIMARY KEYs.
*/
void sqlite3AddPrimaryKey(
  Parse *pParse,    /* Parsing context */
  ExprList *pList,  /* List of field names to be indexed */
  int onError,      /* What to do with a uniqueness conflict */
  int autoInc,      /* True if the AUTOINCREMENT keyword is present */
  int sortOrder     /* SQLITE_SO_ASC or SQLITE_SO_DESC */
){
  Table *pTab = pParse->pNewTable;
  Column *pCol = 0;
  int iCol = -1, i;
  int nTerm;
  if( pTab==0 ) goto primary_key_exit;
  if( pTab->tabFlags & TF_HasPrimaryKey ){
    sqlite3ErrorMsg(pParse,
      "table \"%s\" has more than one primary key", pTab->zName);
    goto primary_key_exit;
  }
  pTab->tabFlags |= TF_HasPrimaryKey;
  if( pList==0 ){
    iCol = pTab->nCol - 1;
    pCol = &pTab->aCol[iCol];
    pCol->colFlags |= COLFLAG_PRIMKEY;
    nTerm = 1;
  }else{
    nTerm = pList->nExpr;
    for(i=0; i<nTerm; i++){
      Expr *pCExpr = sqlite3ExprSkipCollate(pList->a[i].pExpr);
      assert( pCExpr!=0 );
      sqlite3StringToId(pCExpr);
      if( pCExpr->op==TK_ID ){
        const char *zCName = pCExpr->u.zToken;
        for(iCol=0; iCol<pTab->nCol; iCol++){
          if( sqlite3StrICmp(zCName, pTab->aCol[iCol].zName)==0 ){
            pCol = &pTab->aCol[iCol];
            pCol->colFlags |= COLFLAG_PRIMKEY;
            break;
          }
        }
      }
    }
  }
  if( nTerm==1
   && pCol
   && sqlite3StrICmp(sqlite3ColumnType(pCol,""), "INTEGER")==0
   && sortOrder!=SQLITE_SO_DESC
  ){
    if( IN_RENAME_OBJECT && pList ){
      Expr *pCExpr = sqlite3ExprSkipCollate(pList->a[0].pExpr);
      sqlite3RenameTokenRemap(pParse, &pTab->iPKey, pCExpr);
    }
    pTab->iPKey = iCol;
    pTab->keyConf = (u8)onError;
    assert( autoInc==0 || autoInc==1 );
    pTab->tabFlags |= autoInc*TF_Autoincrement;
    if( pList ) pParse->iPkSortOrder = pList->a[0].sortFlags;
  }else if( autoInc ){
#ifndef SQLITE_OMIT_AUTOINCREMENT
    sqlite3ErrorMsg(pParse, "AUTOINCREMENT is only allowed on an "
       "INTEGER PRIMARY KEY");
#endif
  }else{
    sqlite3CreateIndex(pParse, 0, 0, 0, pList, onError, 0,
                           0, sortOrder, 0, SQLITE_IDXTYPE_PRIMARYKEY);
    pList = 0;
  }

primary_key_exit:
  sqlite3ExprListDelete(pParse->db, pList);
  return;
}

/*
** Add a new CHECK constraint to the table currently under construction.
*/
void sqlite3AddCheckConstraint(
  Parse *pParse,    /* Parsing context */
  Expr *pCheckExpr  /* The check expression */
){
#ifndef SQLITE_OMIT_CHECK
  Table *pTab = pParse->pNewTable;
  sqlite3 *db = pParse->db;
  if( pTab && !IN_DECLARE_VTAB
   && !sqlite3BtreeIsReadonly(db->aDb[db->init.iDb].pBt)
  ){
    pTab->pCheck = sqlite3ExprListAppend(pParse, pTab->pCheck, pCheckExpr);
    if( pParse->constraintName.n ){
      sqlite3ExprListSetName(pParse, pTab->pCheck, &pParse->constraintName, 1);
    }
  }else
#endif
  {
    sqlite3ExprDelete(pParse->db, pCheckExpr);
  }
}

/*
** Set the collation function of the most recently parsed table column
** to the CollSeq given.
*/
void sqlite3AddCollateType(Parse *pParse, Token *pToken){
  Table *p;
  int i;
  char *zColl;              /* Dequoted name of collation sequence */
  sqlite3 *db;

  if( (p = pParse->pNewTable)==0 ) return;
  i = p->nCol-1;
  db = pParse->db;
  zColl = sqlite3NameFromToken(db, pToken);
  if( !zColl ) return;

  if( sqlite3LocateCollSeq(pParse, zColl) ){
    Index *pIdx;
    sqlite3DbFree(db, p->aCol[i].zColl);
    p->aCol[i].zColl = zColl;

    /* If the column is declared as "<name> PRIMARY KEY COLLATE <type>",
    ** then an index may have been created on this column before the
    ** collation type was added. Correct this if it is the case.
    */
    for(pIdx=p->pIndex; pIdx; pIdx=pIdx->pNext){
      assert( pIdx->nKeyCol==1 );
      if( pIdx->aiColumn[0]==i ){
        pIdx->azColl[0] = p->aCol[i].zColl;
      }
    }
  }else{
    sqlite3DbFree(db, zColl);
  }
}

/*
** This function returns the collation sequence for database native text
** encoding identified by the string zName, length nName.
**
** If the requested collation sequence is not available, or not available
** in the database native encoding, the collation factory is invoked to
** request it. If the collation factory does not supply such a sequence,
** and the sequence is available in another text encoding, then that is
** returned instead.
**
** If no versions of the requested collations sequence are available, or
** another error occurs, NULL is returned and an error message written into
** pParse.
**
** This routine is a wrapper around sqlite3FindCollSeq().  This routine
** invokes the collation factory if the named collation cannot be found
** and generates an error message.
**
** See also: sqlite3FindCollSeq(), sqlite3GetCollSeq()
*/
CollSeq *sqlite3LocateCollSeq(Parse *pParse, const char *zName){
  sqlite3 *db = pParse->db;
  u8 enc = ENC(db);
  u8 initbusy = db->init.busy;
  CollSeq *pColl;

  pColl = sqlite3FindCollSeq(db, enc, zName, initbusy);
  if( !initbusy && (!pColl || !pColl->xCmp) ){
    pColl = sqlite3GetCollSeq(pParse, enc, pColl, zName);
  }

  return pColl;
}


/*
** Generate code that will increment the schema cookie.
**
** The schema cookie is used to determine when the schema for the
** database changes.  After each schema change, the cookie value
** changes.  When a process first reads the schema it records the
** cookie.  Thereafter, whenever it goes to access the database,
** it checks the cookie to make sure the schema has not changed
** since it was last read.
**
** This plan is not completely bullet-proof.  It is possible for
** the schema to change multiple times and for the cookie to be
** set back to prior value.  But schema changes are infrequent
** and the probability of hitting the same cookie value is only
** 1 chance in 2^32.  So we're safe enough.
**
** IMPLEMENTATION-OF: R-34230-56049 SQLite automatically increments
** the schema-version whenever the schema changes.
*/
void sqlite3ChangeCookie(Parse *pParse, int iDb){
  sqlite3 *db = pParse->db;
  Vdbe *v = pParse->pVdbe;
  assert( sqlite3SchemaMutexHeld(db, iDb, 0) );
  sqlite3VdbeAddOp3(v, OP_SetCookie, iDb, BTREE_SCHEMA_VERSION,
                   (int)(1+(unsigned)db->aDb[iDb].pSchema->schema_cookie));
}

/*
** Measure the number of characters needed to output the given
** identifier.  The number returned includes any quotes used
** but does not include the null terminator.
**
** The estimate is conservative.  It might be larger that what is
** really needed.
*/
static int identLength(const char *z){
  int n;
  for(n=0; *z; n++, z++){
    if( *z=='"' ){ n++; }
  }
  return n + 2;
}

/*
** The first parameter is a pointer to an output buffer. The second
** parameter is a pointer to an integer that contains the offset at
** which to write into the output buffer. This function copies the
** nul-terminated string pointed to by the third parameter, zSignedIdent,
** to the specified offset in the buffer and updates *pIdx to refer
** to the first byte after the last byte written before returning.
**
** If the string zSignedIdent consists entirely of alpha-numeric
** characters, does not begin with a digit and is not an SQL keyword,
** then it is copied to the output buffer exactly as it is. Otherwise,
** it is quoted using double-quotes.
*/
static void identPut(char *z, int *pIdx, char *zSignedIdent){
  unsigned char *zIdent = (unsigned char*)zSignedIdent;
  int i, j, needQuote;
  i = *pIdx;

  for(j=0; zIdent[j]; j++){
    if( !sqlite3Isalnum(zIdent[j]) && zIdent[j]!='_' ) break;
  }
  needQuote = sqlite3Isdigit(zIdent[0])
            || sqlite3KeywordCode(zIdent, j)!=TK_ID
            || zIdent[j]!=0
            || j==0;

  if( needQuote ) z[i++] = '"';
  for(j=0; zIdent[j]; j++){
    z[i++] = zIdent[j];
    if( zIdent[j]=='"' ) z[i++] = '"';
  }
  if( needQuote ) z[i++] = '"';
  z[i] = 0;
  *pIdx = i;
}

/*
** Generate a CREATE TABLE statement appropriate for the given
** table.  Memory to hold the text of the statement is obtained
** from sqliteMalloc() and must be freed by the calling function.
*/
static char *createTableStmt(sqlite3 *db, Table *p){
  int i, k, n;
  char *zStmt;
  char *zSep, *zSep2, *zEnd;
  Column *pCol;
  n = 0;
  for(pCol = p->aCol, i=0; i<p->nCol; i++, pCol++){
    n += identLength(pCol->zName) + 5;
  }
  n += identLength(p->zName);
  if( n<50 ){
    zSep = "";
    zSep2 = ",";
    zEnd = ")";
  }else{
    zSep = "\n  ";
    zSep2 = ",\n  ";
    zEnd = "\n)";
  }
  n += 35 + 6*p->nCol;
  zStmt = sqlite3DbMallocRaw(0, n);
  if( zStmt==0 ){
    sqlite3OomFault(db);
    return 0;
  }
  sqlite3_snprintf(n, zStmt, "CREATE TABLE ");
  k = sqlite3Strlen30(zStmt);
  identPut(zStmt, &k, p->zName);
  zStmt[k++] = '(';
  for(pCol=p->aCol, i=0; i<p->nCol; i++, pCol++){
    static const char * const azType[] = {
        /* SQLITE_AFF_BLOB    */ "",
        /* SQLITE_AFF_TEXT    */ " TEXT",
        /* SQLITE_AFF_NUMERIC */ " NUM",
        /* SQLITE_AFF_INTEGER */ " INT",
        /* SQLITE_AFF_REAL    */ " REAL"
    };
    int len;
    const char *zType;

    sqlite3_snprintf(n-k, &zStmt[k], zSep);
    k += sqlite3Strlen30(&zStmt[k]);
    zSep = zSep2;
    identPut(zStmt, &k, pCol->zName);
    assert( pCol->affinity-SQLITE_AFF_BLOB >= 0 );
    assert( pCol->affinity-SQLITE_AFF_BLOB < ArraySize(azType) );
    testcase( pCol->affinity==SQLITE_AFF_BLOB );
    testcase( pCol->affinity==SQLITE_AFF_TEXT );
    testcase( pCol->affinity==SQLITE_AFF_NUMERIC );
    testcase( pCol->affinity==SQLITE_AFF_INTEGER );
    testcase( pCol->affinity==SQLITE_AFF_REAL );

    zType = azType[pCol->affinity - SQLITE_AFF_BLOB];
    len = sqlite3Strlen30(zType);
    assert( pCol->affinity==SQLITE_AFF_BLOB
            || pCol->affinity==sqlite3AffinityType(zType, 0) );
    memcpy(&zStmt[k], zType, len);
    k += len;
    assert( k<=n );
  }
  sqlite3_snprintf(n-k, &zStmt[k], "%s", zEnd);
  return zStmt;
}

/*
** Resize an Index object to hold N columns total.  Return SQLITE_OK
** on success and SQLITE_NOMEM on an OOM error.
*/
static int resizeIndexObject(sqlite3 *db, Index *pIdx, int N){
  char *zExtra;
  int nByte;
  if( pIdx->nColumn>=N ) return SQLITE_OK;
  assert( pIdx->isResized==0 );
  nByte = (sizeof(char*) + sizeof(i16) + 1)*N;
  zExtra = sqlite3DbMallocZero(db, nByte);
  if( zExtra==0 ) return SQLITE_NOMEM_BKPT;
  memcpy(zExtra, pIdx->azColl, sizeof(char*)*pIdx->nColumn);
  pIdx->azColl = (const char**)zExtra;
  zExtra += sizeof(char*)*N;
  memcpy(zExtra, pIdx->aiColumn, sizeof(i16)*pIdx->nColumn);
  pIdx->aiColumn = (i16*)zExtra;
  zExtra += sizeof(i16)*N;
  memcpy(zExtra, pIdx->aSortOrder, pIdx->nColumn);
  pIdx->aSortOrder = (u8*)zExtra;
  pIdx->nColumn = N;
  pIdx->isResized = 1;
  return SQLITE_OK;
}

/*
** Estimate the total row width for a table.
*/
static void estimateTableWidth(Table *pTab){
  unsigned wTable = 0;
  const Column *pTabCol;
  int i;
  for(i=pTab->nCol, pTabCol=pTab->aCol; i>0; i--, pTabCol++){
    wTable += pTabCol->szEst;
  }
  if( pTab->iPKey<0 ) wTable++;
  pTab->szTabRow = sqlite3LogEst(wTable*4);
}

/*
** Estimate the average size of a row for an index.
*/
static void estimateIndexWidth(Index *pIdx){
  unsigned wIndex = 0;
  int i;
  const Column *aCol = pIdx->pTable->aCol;
  for(i=0; i<pIdx->nColumn; i++){
    i16 x = pIdx->aiColumn[i];
    assert( x<pIdx->pTable->nCol );
    wIndex += x<0 ? 1 : aCol[pIdx->aiColumn[i]].szEst;
  }
  pIdx->szIdxRow = sqlite3LogEst(wIndex*4);
}

/* Return true if column number x is any of the first nCol entries of aiCol[].
** This is used to determine if the column number x appears in any of the
** first nCol entries of an index.
*/
static int hasColumn(const i16 *aiCol, int nCol, int x){
  while( nCol-- > 0 ){
    assert( aiCol[0]>=0 );
    if( x==*(aiCol++) ){
      return 1;
    }
  }
  return 0;
}

/*
** Return true if any of the first nKey entries of index pIdx exactly
** match the iCol-th entry of pPk.  pPk is always a WITHOUT ROWID
** PRIMARY KEY index.  pIdx is an index on the same table.  pIdx may
** or may not be the same index as pPk.
**
** The first nKey entries of pIdx are guaranteed to be ordinary columns,
** not a rowid or expression.
**
** This routine differs from hasColumn() in that both the column and the
** collating sequence must match for this routine, but for hasColumn() only
** the column name must match.
*/
static int isDupColumn(Index *pIdx, int nKey, Index *pPk, int iCol){
  int i, j;
  assert( nKey<=pIdx->nColumn );
  assert( iCol<MAX(pPk->nColumn,pPk->nKeyCol) );
  assert( pPk->idxType==SQLITE_IDXTYPE_PRIMARYKEY );
  assert( pPk->pTable->tabFlags & TF_WithoutRowid );
  assert( pPk->pTable==pIdx->pTable );
  testcase( pPk==pIdx );
  j = pPk->aiColumn[iCol];
  assert( j!=XN_ROWID && j!=XN_EXPR );
  for(i=0; i<nKey; i++){
    assert( pIdx->aiColumn[i]>=0 || j>=0 );
    if( pIdx->aiColumn[i]==j
     && sqlite3StrICmp(pIdx->azColl[i], pPk->azColl[iCol])==0
    ){
      return 1;
    }
  }
  return 0;
}

/* Recompute the colNotIdxed field of the Index.
**
** colNotIdxed is a bitmask that has a 0 bit representing each indexed
** columns that are within the first 63 columns of the table.  The
** high-order bit of colNotIdxed is always 1.  All unindexed columns
** of the table have a 1.
**
** The colNotIdxed mask is AND-ed with the SrcList.a[].colUsed mask
** to determine if the index is covering index.
*/
static void recomputeColumnsNotIndexed(Index *pIdx){
  Bitmask m = 0;
  int j;
  for(j=pIdx->nColumn-1; j>=0; j--){
    int x = pIdx->aiColumn[j];
    if( x>=0 ){
      testcase( x==BMS-1 );
      testcase( x==BMS-2 );
      if( x<BMS-1 ) m |= MASKBIT(x);
    }
  }
  pIdx->colNotIdxed = ~m;
  assert( (pIdx->colNotIdxed>>63)==1 );
}

/*
** This routine runs at the end of parsing a CREATE TABLE statement that
** has a WITHOUT ROWID clause.  The job of this routine is to convert both
** internal schema data structures and the generated VDBE code so that they
** are appropriate for a WITHOUT ROWID table instead of a rowid table.
** Changes include:
**
**     (1)  Set all columns of the PRIMARY KEY schema object to be NOT NULL.
**     (2)  Convert P3 parameter of the OP_CreateBtree from BTREE_INTKEY
**          into BTREE_BLOBKEY.
**     (3)  Bypass the creation of the sqlite_master table entry
**          for the PRIMARY KEY as the primary key index is now
**          identified by the sqlite_master table entry of the table itself.
**     (4)  Set the Index.tnum of the PRIMARY KEY Index object in the
**          schema to the rootpage from the main table.
**     (5)  Add all table columns to the PRIMARY KEY Index object
**          so that the PRIMARY KEY is a covering index.  The surplus
**          columns are part of KeyInfo.nAllField and are not used for
**          sorting or lookup or uniqueness checks.
**     (6)  Replace the rowid tail on all automatically generated UNIQUE
**          indices with the PRIMARY KEY columns.
**
** For virtual tables, only (1) is performed.
*/
static void convertToWithoutRowidTable(Parse *pParse, Table *pTab){
  Index *pIdx;
  Index *pPk;
  int nPk;
  int nExtra;
  int i, j;
  sqlite3 *db = pParse->db;
  Vdbe *v = pParse->pVdbe;

  /* Mark every PRIMARY KEY column as NOT NULL (except for imposter tables)
  */
  if( !db->init.imposterTable ){
    for(i=0; i<pTab->nCol; i++){
      if( (pTab->aCol[i].colFlags & COLFLAG_PRIMKEY)!=0 ){
        pTab->aCol[i].notNull = OE_Abort;
      }
    }
  }

  /* Convert the P3 operand of the OP_CreateBtree opcode from BTREE_INTKEY
  ** into BTREE_BLOBKEY.
  */
  if( pParse->addrCrTab ){
    assert( v );
    sqlite3VdbeChangeP3(v, pParse->addrCrTab, BTREE_BLOBKEY);
  }

  /* Locate the PRIMARY KEY index.  Or, if this table was originally
  ** an INTEGER PRIMARY KEY table, create a new PRIMARY KEY index.
  */
  if( pTab->iPKey>=0 ){
    ExprList *pList;
    Token ipkToken;
    sqlite3TokenInit(&ipkToken, pTab->aCol[pTab->iPKey].zName);
    pList = sqlite3ExprListAppend(pParse, 0,
                  sqlite3ExprAlloc(db, TK_ID, &ipkToken, 0));
    if( pList==0 ) return;
    if( IN_RENAME_OBJECT ){
      sqlite3RenameTokenRemap(pParse, pList->a[0].pExpr, &pTab->iPKey);
    }
    pList->a[0].sortFlags = pParse->iPkSortOrder;
    assert( pParse->pNewTable==pTab );
    pTab->iPKey = -1;
    sqlite3CreateIndex(pParse, 0, 0, 0, pList, pTab->keyConf, 0, 0, 0, 0,
                       SQLITE_IDXTYPE_PRIMARYKEY);
    if( db->mallocFailed || pParse->nErr ) return;
    pPk = sqlite3PrimaryKeyIndex(pTab);
    assert( pPk->nKeyCol==1 );
  }else{
    pPk = sqlite3PrimaryKeyIndex(pTab);
    assert( pPk!=0 );

    /*
    ** Remove all redundant columns from the PRIMARY KEY.  For example, change
    ** "PRIMARY KEY(a,b,a,b,c,b,c,d)" into just "PRIMARY KEY(a,b,c,d)".  Later
    ** code assumes the PRIMARY KEY contains no repeated columns.
    */
    for(i=j=1; i<pPk->nKeyCol; i++){
      if( isDupColumn(pPk, j, pPk, i) ){
        pPk->nColumn--;
      }else{
        testcase( hasColumn(pPk->aiColumn, j, pPk->aiColumn[i]) );
        pPk->azColl[j] = pPk->azColl[i];
        pPk->aSortOrder[j] = pPk->aSortOrder[i];
        pPk->aiColumn[j++] = pPk->aiColumn[i];
      }
    }
    pPk->nKeyCol = j;
  }
  assert( pPk!=0 );
  pPk->isCovering = 1;
  if( !db->init.imposterTable ) pPk->uniqNotNull = 1;
  nPk = pPk->nColumn = pPk->nKeyCol;

  /* Bypass the creation of the PRIMARY KEY btree and the sqlite_master
  ** table entry. This is only required if currently generating VDBE
  ** code for a CREATE TABLE (not when parsing one as part of reading
  ** a database schema).  */
  if( v && pPk->tnum>0 ){
    assert( db->init.busy==0 );
    sqlite3VdbeChangeOpcode(v, pPk->tnum, OP_Goto);
  }

  /* The root page of the PRIMARY KEY is the table root page */
  pPk->tnum = pTab->tnum;

  /* Update the in-memory representation of all UNIQUE indices by converting
  ** the final rowid column into one or more columns of the PRIMARY KEY.
  */
  for(pIdx=pTab->pIndex; pIdx; pIdx=pIdx->pNext){
    int n;
    if( IsPrimaryKeyIndex(pIdx) ) continue;
    for(i=n=0; i<nPk; i++){
      if( !isDupColumn(pIdx, pIdx->nKeyCol, pPk, i) ){
        testcase( hasColumn(pIdx->aiColumn, pIdx->nKeyCol, pPk->aiColumn[i]) );
        n++;
      }
    }
    if( n==0 ){
      /* This index is a superset of the primary key */
      pIdx->nColumn = pIdx->nKeyCol;
      continue;
    }
    if( resizeIndexObject(db, pIdx, pIdx->nKeyCol+n) ) return;
    for(i=0, j=pIdx->nKeyCol; i<nPk; i++){
      if( !isDupColumn(pIdx, pIdx->nKeyCol, pPk, i) ){
        testcase( hasColumn(pIdx->aiColumn, pIdx->nKeyCol, pPk->aiColumn[i]) );
        pIdx->aiColumn[j] = pPk->aiColumn[i];
        pIdx->azColl[j] = pPk->azColl[i];
        if( pPk->aSortOrder[i] ){
          /* See ticket https://www.sqlite.org/src/info/bba7b69f9849b5bf */
          pIdx->bAscKeyBug = 1;
        }
        j++;
      }
    }
    assert( pIdx->nColumn>=pIdx->nKeyCol+n );
    assert( pIdx->nColumn>=j );
  }

  /* Add all table columns to the PRIMARY KEY index
  */
  nExtra = 0;
  for(i=0; i<pTab->nCol; i++){
    if( !hasColumn(pPk->aiColumn, nPk, i) ) nExtra++;
  }
  if( resizeIndexObject(db, pPk, nPk+nExtra) ) return;
  for(i=0, j=nPk; i<pTab->nCol; i++){
    if( !hasColumn(pPk->aiColumn, j, i) ){
      assert( j<pPk->nColumn );
      pPk->aiColumn[j] = i;
      pPk->azColl[j] = sqlite3StrBINARY;
      j++;
    }
  }
  assert( pPk->nColumn==j );
  assert( pTab->nCol<=j );
  recomputeColumnsNotIndexed(pPk);
}

#ifndef SQLITE_OMIT_VIRTUALTABLE
/*
** Return true if zName is a shadow table name in the current database
** connection.
**
** zName is temporarily modified while this routine is running, but is
** restored to its original value prior to this routine returning.
*/
static int isShadowTableName(sqlite3 *db, char *zName){
  char *zTail;                  /* Pointer to the last "_" in zName */
  Table *pTab;                  /* Table that zName is a shadow of */
  Module *pMod;                 /* Module for the virtual table */

  zTail = strrchr(zName, '_');
  if( zTail==0 ) return 0;
  *zTail = 0;
  pTab = sqlite3FindTable(db, zName, 0);
  *zTail = '_';
  if( pTab==0 ) return 0;
  if( !IsVirtual(pTab) ) return 0;
  pMod = (Module*)sqlite3HashFind(&db->aModule, pTab->azModuleArg[0]);
  if( pMod==0 ) return 0;
  if( pMod->pModule->iVersion<3 ) return 0;
  if( pMod->pModule->xShadowName==0 ) return 0;
  return pMod->pModule->xShadowName(zTail+1);
}
#else
# define isShadowTableName(x,y) 0
#endif /* ifndef SQLITE_OMIT_VIRTUALTABLE */

/*
** This routine is called to report the final ")" that terminates
** a CREATE TABLE statement.
**
** The table structure that other action routines have been building
** is added to the internal hash tables, assuming no errors have
** occurred.
**
** An entry for the table is made in the master table on disk, unless
** this is a temporary table or db->init.busy==1.  When db->init.busy==1
** it means we are reading the sqlite_master table because we just
** connected to the database or because the sqlite_master table has
** recently changed, so the entry for this table already exists in
** the sqlite_master table.  We do not want to create it again.
**
** If the pSelect argument is not NULL, it means that this routine
** was called to create a table generated from a
** "CREATE TABLE ... AS SELECT ..." statement.  The column names of
** the new table will match the result set of the SELECT.
*/
void sqlite3EndTable(
  Parse *pParse,          /* Parse context */
  Token *pCons,           /* The ',' token after the last column defn. */
  Token *pEnd,            /* The ')' before options in the CREATE TABLE */
  u8 tabOpts,             /* Extra table options. Usually 0. */
  Select *pSelect         /* Select from a "CREATE ... AS SELECT" */
){
  Table *p;                 /* The new table */
  sqlite3 *db = pParse->db; /* The database connection */
  int iDb;                  /* Database in which the table lives */
  Index *pIdx;              /* An implied index of the table */

  if( pEnd==0 && pSelect==0 ){
    return;
  }
  assert( !db->mallocFailed );
  p = pParse->pNewTable;
  if( p==0 ) return;

  if( pSelect==0 && isShadowTableName(db, p->zName) ){
    p->tabFlags |= TF_Shadow;
  }

  /* If the db->init.busy is 1 it means we are reading the SQL off the
  ** "sqlite_master" or "sqlite_temp_master" table on the disk.
  ** So do not write to the disk again.  Extract the root page number
  ** for the table from the db->init.newTnum field.  (The page number
  ** should have been put there by the sqliteOpenCb routine.)
  **
  ** If the root page number is 1, that means this is the sqlite_master
  ** table itself.  So mark it read-only.
  */
  if( db->init.busy ){
    if( pSelect ){
      sqlite3ErrorMsg(pParse, "");
      return;
    }
    p->tnum = db->init.newTnum;
    if( p->tnum==1 ) p->tabFlags |= TF_Readonly;
  }

  assert( (p->tabFlags & TF_HasPrimaryKey)==0
       || p->iPKey>=0 || sqlite3PrimaryKeyIndex(p)!=0 );
  assert( (p->tabFlags & TF_HasPrimaryKey)!=0
       || (p->iPKey<0 && sqlite3PrimaryKeyIndex(p)==0) );

  /* Special processing for WITHOUT ROWID Tables */
  if( tabOpts & TF_WithoutRowid ){
    if( (p->tabFlags & TF_Autoincrement) ){
      sqlite3ErrorMsg(pParse,
          "AUTOINCREMENT not allowed on WITHOUT ROWID tables");
      return;
    }
    if( (p->tabFlags & TF_HasPrimaryKey)==0 ){
      sqlite3ErrorMsg(pParse, "PRIMARY KEY missing on table %s", p->zName);
    }else{
      p->tabFlags |= TF_WithoutRowid | TF_NoVisibleRowid;
      convertToWithoutRowidTable(pParse, p);
    }
  }

  iDb = sqlite3SchemaToIndex(db, p->pSchema);

#ifndef SQLITE_OMIT_CHECK
  /* Resolve names in all CHECK constraint expressions.
  */
  if( p->pCheck ){
    sqlite3ResolveSelfReference(pParse, p, NC_IsCheck, 0, p->pCheck);
  }
#endif /* !defined(SQLITE_OMIT_CHECK) */

  /* Estimate the average row size for the table and for all implied indices */
  estimateTableWidth(p);
  for(pIdx=p->pIndex; pIdx; pIdx=pIdx->pNext){
    estimateIndexWidth(pIdx);
  }

  /* If not initializing, then create a record for the new table
  ** in the SQLITE_MASTER table of the database.
  **
  ** If this is a TEMPORARY table, write the entry into the auxiliary
  ** file instead of into the main database file.
  */
  if( !db->init.busy ){
    int n;
    Vdbe *v;
    char *zType;    /* "view" or "table" */
    char *zType2;   /* "VIEW" or "TABLE" */
    char *zStmt;    /* Text of the CREATE TABLE or CREATE VIEW statement */

    v = sqlite3GetVdbe(pParse);
    if( NEVER(v==0) ) return;

    sqlite3VdbeAddOp1(v, OP_Close, 0);

    /*
    ** Initialize zType for the new view or table.
    */
    if( p->pSelect==0 ){
      /* A regular table */
      zType = "table";
      zType2 = "TABLE";
#ifndef SQLITE_OMIT_VIEW
    }else{
      /* A view */
      zType = "view";
      zType2 = "VIEW";
#endif
    }

    /* If this is a CREATE TABLE xx AS SELECT ..., execute the SELECT
    ** statement to populate the new table. The root-page number for the
    ** new table is in register pParse->regRoot.
    **
    ** Once the SELECT has been coded by sqlite3Select(), it is in a
    ** suitable state to query for the column names and types to be used
    ** by the new table.
    **
    ** A shared-cache write-lock is not required to write to the new table,
    ** as a schema-lock must have already been obtained to create it. Since
    ** a schema-lock excludes all other database users, the write-lock would
    ** be redundant.
    */
    if( pSelect ){
      SelectDest dest;    /* Where the SELECT should store results */
      int regYield;       /* Register holding co-routine entry-point */
      int addrTop;        /* Top of the co-routine */
      int regRec;         /* A record to be insert into the new table */
      int regRowid;       /* Rowid of the next row to insert */
      int addrInsLoop;    /* Top of the loop for inserting rows */
      Table *pSelTab;     /* A table that describes the SELECT results */

      regYield = ++pParse->nMem;
      regRec = ++pParse->nMem;
      regRowid = ++pParse->nMem;
      assert(pParse->nTab==1);
      sqlite3MayAbort(pParse);
      sqlite3VdbeAddOp3(v, OP_OpenWrite, 1, pParse->regRoot, iDb);
      sqlite3VdbeChangeP5(v, OPFLAG_P2ISREG);
      pParse->nTab = 2;
      addrTop = sqlite3VdbeCurrentAddr(v) + 1;
      sqlite3VdbeAddOp3(v, OP_InitCoroutine, regYield, 0, addrTop);
      if( pParse->nErr ) return;
      pSelTab = sqlite3ResultSetOfSelect(pParse, pSelect, SQLITE_AFF_BLOB);
      if( pSelTab==0 ) return;
      assert( p->aCol==0 );
      p->nCol = pSelTab->nCol;
      p->aCol = pSelTab->aCol;
      pSelTab->nCol = 0;
      pSelTab->aCol = 0;
      sqlite3DeleteTable(db, pSelTab);
      sqlite3SelectDestInit(&dest, SRT_Coroutine, regYield);
      sqlite3Select(pParse, pSelect, &dest);
      if( pParse->nErr ) return;
      sqlite3VdbeEndCoroutine(v, regYield);
      sqlite3VdbeJumpHere(v, addrTop - 1);
      addrInsLoop = sqlite3VdbeAddOp1(v, OP_Yield, dest.iSDParm);
      VdbeCoverage(v);
      sqlite3VdbeAddOp3(v, OP_MakeRecord, dest.iSdst, dest.nSdst, regRec);
      sqlite3TableAffinity(v, p, 0);
      sqlite3VdbeAddOp2(v, OP_NewRowid, 1, regRowid);
      sqlite3VdbeAddOp3(v, OP_Insert, 1, regRec, regRowid);
      sqlite3VdbeGoto(v, addrInsLoop);
      sqlite3VdbeJumpHere(v, addrInsLoop);
      sqlite3VdbeAddOp1(v, OP_Close, 1);
    }

    /* Compute the complete text of the CREATE statement */
    if( pSelect ){
      zStmt = createTableStmt(db, p);
    }else{
      Token *pEnd2 = tabOpts ? &pParse->sLastToken : pEnd;
      n = (int)(pEnd2->z - pParse->sNameToken.z);
      if( pEnd2->z[0]!=';' ) n += pEnd2->n;
      zStmt = sqlite3MPrintf(db,
          "CREATE %s %.*s", zType2, n, pParse->sNameToken.z
      );
    }

    /* A slot for the record has already been allocated in the
    ** SQLITE_MASTER table.  We just need to update that slot with all
    ** the information we've collected.
    */
    sqlite3NestedParse(pParse,
      "UPDATE %Q.%s "
         "SET type='%s', name=%Q, tbl_name=%Q, rootpage=#%d, sql=%Q "
       "WHERE rowid=#%d",
      db->aDb[iDb].zDbSName, MASTER_NAME,
      zType,
      p->zName,
      p->zName,
      pParse->regRoot,
      zStmt,
      pParse->regRowid
    );
    sqlite3DbFree(db, zStmt);
    sqlite3ChangeCookie(pParse, iDb);

#ifndef SQLITE_OMIT_AUTOINCREMENT
    /* Check to see if we need to create an sqlite_sequence table for
    ** keeping track of autoincrement keys.
    */
    if( (p->tabFlags & TF_Autoincrement)!=0 ){
      Db *pDb = &db->aDb[iDb];
      assert( sqlite3SchemaMutexHeld(db, iDb, 0) );
      if( pDb->pSchema->pSeqTab==0 ){
        sqlite3NestedParse(pParse,
          "CREATE TABLE %Q.sqlite_sequence(name,seq)",
          pDb->zDbSName
        );
      }
    }
#endif

    /* Reparse everything to update our internal data structures */
    sqlite3VdbeAddParseSchemaOp(v, iDb,
           sqlite3MPrintf(db, "tbl_name='%q' AND type!='trigger'", p->zName));
  }


  /* Add the table to the in-memory representation of the database.
  */
  if( db->init.busy ){
    Table *pOld;
    Schema *pSchema = p->pSchema;
    assert( sqlite3SchemaMutexHeld(db, iDb, 0) );
    pOld = sqlite3HashInsert(&pSchema->tblHash, p->zName, p);
    if( pOld ){
      assert( p==pOld );  /* Malloc must have failed inside HashInsert() */
      sqlite3OomFault(db);
      return;
    }
    pParse->pNewTable = 0;
    db->mDbFlags |= DBFLAG_SchemaChange;

#ifndef SQLITE_OMIT_ALTERTABLE
    if( !p->pSelect ){
      const char *zName = (const char *)pParse->sNameToken.z;
      int nName;
      assert( !pSelect && pCons && pEnd );
      if( pCons->z==0 ){
        pCons = pEnd;
      }
      nName = (int)((const char *)pCons->z - zName);
      p->addColOffset = 13 + sqlite3Utf8CharLen(zName, nName);
    }
#endif
  }
}

#ifndef SQLITE_OMIT_VIEW
/*
** The parser calls this routine in order to create a new VIEW
*/
void sqlite3CreateView(
  Parse *pParse,     /* The parsing context */
  Token *pBegin,     /* The CREATE token that begins the statement */
  Token *pName1,     /* The token that holds the name of the view */
  Token *pName2,     /* The token that holds the name of the view */
  ExprList *pCNames, /* Optional list of view column names */
  Select *pSelect,   /* A SELECT statement that will become the new view */
  int isTemp,        /* TRUE for a TEMPORARY view */
  int noErr          /* Suppress error messages if VIEW already exists */
){
  Table *p;
  int n;
  const char *z;
  Token sEnd;
  DbFixer sFix;
  Token *pName = 0;
  int iDb;
  sqlite3 *db = pParse->db;

  if( pParse->nVar>0 ){
    sqlite3ErrorMsg(pParse, "parameters are not allowed in views");
    goto create_view_fail;
  }
  sqlite3StartTable(pParse, pName1, pName2, isTemp, 1, 0, noErr);
  p = pParse->pNewTable;
  if( p==0 || pParse->nErr ) goto create_view_fail;
  sqlite3TwoPartName(pParse, pName1, pName2, &pName);
  iDb = sqlite3SchemaToIndex(db, p->pSchema);
  sqlite3FixInit(&sFix, pParse, iDb, "view", pName);
  if( sqlite3FixSelect(&sFix, pSelect) ) goto create_view_fail;

  /* Make a copy of the entire SELECT statement that defines the view.
  ** This will force all the Expr.token.z values to be dynamically
  ** allocated rather than point to the input string - which means that
  ** they will persist after the current sqlite3_exec() call returns.
  */
  if( IN_RENAME_OBJECT ){
    p->pSelect = pSelect;
    pSelect = 0;
  }else{
    p->pSelect = sqlite3SelectDup(db, pSelect, EXPRDUP_REDUCE);
  }
  p->pCheck = sqlite3ExprListDup(db, pCNames, EXPRDUP_REDUCE);
  if( db->mallocFailed ) goto create_view_fail;

  /* Locate the end of the CREATE VIEW statement.  Make sEnd point to
  ** the end.
  */
  sEnd = pParse->sLastToken;
  assert( sEnd.z[0]!=0 || sEnd.n==0 );
  if( sEnd.z[0]!=';' ){
    sEnd.z += sEnd.n;
  }
  sEnd.n = 0;
  n = (int)(sEnd.z - pBegin->z);
  assert( n>0 );
  z = pBegin->z;
  while( sqlite3Isspace(z[n-1]) ){ n--; }
  sEnd.z = &z[n-1];
  sEnd.n = 1;

  /* Use sqlite3EndTable() to add the view to the SQLITE_MASTER table */
  sqlite3EndTable(pParse, 0, &sEnd, 0, 0);

create_view_fail:
  sqlite3SelectDelete(db, pSelect);
  if( IN_RENAME_OBJECT ){
    sqlite3RenameExprlistUnmap(pParse, pCNames);
  }
  sqlite3ExprListDelete(db, pCNames);
  return;
}
#endif /* SQLITE_OMIT_VIEW */

#if !defined(SQLITE_OMIT_VIEW) || !defined(SQLITE_OMIT_VIRTUALTABLE)
/*
** The Table structure pTable is really a VIEW.  Fill in the names of
** the columns of the view in the pTable structure.  Return the number
** of errors.  If an error is seen leave an error message in pParse->zErrMsg.
*/
int sqlite3ViewGetColumnNames(Parse *pParse, Table *pTable){
  Table *pSelTab;   /* A fake table from which we get the result set */
  Select *pSel;     /* Copy of the SELECT that implements the view */
  int nErr = 0;     /* Number of errors encountered */
  int n;            /* Temporarily holds the number of cursors assigned */
  sqlite3 *db = pParse->db;  /* Database connection for malloc errors */
#ifndef SQLITE_OMIT_VIRTUALTABLE
  int rc;
#endif
#ifndef SQLITE_OMIT_AUTHORIZATION
  sqlite3_xauth xAuth;       /* Saved xAuth pointer */
#endif

  assert( pTable );

#ifndef SQLITE_OMIT_VIRTUALTABLE
  db->nSchemaLock++;
  rc = sqlite3VtabCallConnect(pParse, pTable);
  db->nSchemaLock--;
  if( rc ){
    return 1;
  }
  if( IsVirtual(pTable) ) return 0;
#endif

#ifndef SQLITE_OMIT_VIEW
  /* A positive nCol means the columns names for this view are
  ** already known.
  */
  if( pTable->nCol>0 ) return 0;

  /* A negative nCol is a special marker meaning that we are currently
  ** trying to compute the column names.  If we enter this routine with
  ** a negative nCol, it means two or more views form a loop, like this:
  **
  **     CREATE VIEW one AS SELECT * FROM two;
  **     CREATE VIEW two AS SELECT * FROM one;
  **
  ** Actually, the error above is now caught prior to reaching this point.
  ** But the following test is still important as it does come up
  ** in the following:
  **
  **     CREATE TABLE main.ex1(a);
  **     CREATE TEMP VIEW ex1 AS SELECT a FROM ex1;
  **     SELECT * FROM temp.ex1;
  */
  if( pTable->nCol<0 ){
    sqlite3ErrorMsg(pParse, "view %s is circularly defined", pTable->zName);
    return 1;
  }
  assert( pTable->nCol>=0 );

  /* If we get this far, it means we need to compute the table names.
  ** Note that the call to sqlite3ResultSetOfSelect() will expand any
  ** "*" elements in the results set of the view and will assign cursors
  ** to the elements of the FROM clause.  But we do not want these changes
  ** to be permanent.  So the computation is done on a copy of the SELECT
  ** statement that defines the view.
  */
  assert( pTable->pSelect );
  pSel = sqlite3SelectDup(db, pTable->pSelect, 0);
  if( pSel ){
#ifndef SQLITE_OMIT_ALTERTABLE
    u8 eParseMode = pParse->eParseMode;
    pParse->eParseMode = PARSE_MODE_NORMAL;
#endif
    n = pParse->nTab;
    sqlite3SrcListAssignCursors(pParse, pSel->pSrc);
    pTable->nCol = -1;
    DisableLookaside;
#ifndef SQLITE_OMIT_AUTHORIZATION
    xAuth = db->xAuth;
    db->xAuth = 0;
    pSelTab = sqlite3ResultSetOfSelect(pParse, pSel, SQLITE_AFF_NONE);
    db->xAuth = xAuth;
#else
    pSelTab = sqlite3ResultSetOfSelect(pParse, pSel, SQLITE_AFF_NONE);
#endif
    pParse->nTab = n;
    if( pTable->pCheck ){
      /* CREATE VIEW name(arglist) AS ...
      ** The names of the columns in the table are taken from
      ** arglist which is stored in pTable->pCheck.  The pCheck field
      ** normally holds CHECK constraints on an ordinary table, but for
      ** a VIEW it holds the list of column names.
      */
      sqlite3ColumnsFromExprList(pParse, pTable->pCheck,
                                 &pTable->nCol, &pTable->aCol);
      if( db->mallocFailed==0
       && pParse->nErr==0
       && pTable->nCol==pSel->pEList->nExpr
      ){
        sqlite3SelectAddColumnTypeAndCollation(pParse, pTable, pSel,
                                               SQLITE_AFF_NONE);
      }
    }else if( pSelTab ){
      /* CREATE VIEW name AS...  without an argument list.  Construct
      ** the column names from the SELECT statement that defines the view.
      */
      assert( pTable->aCol==0 );
      pTable->nCol = pSelTab->nCol;
      pTable->aCol = pSelTab->aCol;
      pSelTab->nCol = 0;
      pSelTab->aCol = 0;
      assert( sqlite3SchemaMutexHeld(db, 0, pTable->pSchema) );
    }else{
      pTable->nCol = 0;
      nErr++;
    }
    sqlite3DeleteTable(db, pSelTab);
    sqlite3SelectDelete(db, pSel);
    EnableLookaside;
#ifndef SQLITE_OMIT_ALTERTABLE
    pParse->eParseMode = eParseMode;
#endif
  } else {
    nErr++;
  }
  pTable->pSchema->schemaFlags |= DB_UnresetViews;
  if( db->mallocFailed ){
    sqlite3DeleteColumnNames(db, pTable);
    pTable->aCol = 0;
    pTable->nCol = 0;
  }
#endif /* SQLITE_OMIT_VIEW */
  return nErr;
}
#endif /* !defined(SQLITE_OMIT_VIEW) || !defined(SQLITE_OMIT_VIRTUALTABLE) */

#ifndef SQLITE_OMIT_VIEW
/*
** Clear the column names from every VIEW in database idx.
*/
static void sqliteViewResetAll(sqlite3 *db, int idx){
  HashElem *i;
  assert( sqlite3SchemaMutexHeld(db, idx, 0) );
  if( !DbHasProperty(db, idx, DB_UnresetViews) ) return;
  for(i=sqliteHashFirst(&db->aDb[idx].pSchema->tblHash); i;i=sqliteHashNext(i)){
    Table *pTab = sqliteHashData(i);
    if( pTab->pSelect ){
      sqlite3DeleteColumnNames(db, pTab);
      pTab->aCol = 0;
      pTab->nCol = 0;
    }
  }
  DbClearProperty(db, idx, DB_UnresetViews);
}
#else
# define sqliteViewResetAll(A,B)
#endif /* SQLITE_OMIT_VIEW */

/*
** This function is called by the VDBE to adjust the internal schema
** used by SQLite when the btree layer moves a table root page. The
** root-page of a table or index in database iDb has changed from iFrom
** to iTo.
**
** Ticket #1728:  The symbol table might still contain information
** on tables and/or indices that are the process of being deleted.
** If you are unlucky, one of those deleted indices or tables might
** have the same rootpage number as the real table or index that is
** being moved.  So we cannot stop searching after the first match
** because the first match might be for one of the deleted indices
** or tables and not the table/index that is actually being moved.
** We must continue looping until all tables and indices with
** rootpage==iFrom have been converted to have a rootpage of iTo
** in order to be certain that we got the right one.
*/
#ifndef SQLITE_OMIT_AUTOVACUUM
void sqlite3RootPageMoved(sqlite3 *db, int iDb, int iFrom, int iTo){
  HashElem *pElem;
  Hash *pHash;
  Db *pDb;

  assert( sqlite3SchemaMutexHeld(db, iDb, 0) );
  pDb = &db->aDb[iDb];
  pHash = &pDb->pSchema->tblHash;
  for(pElem=sqliteHashFirst(pHash); pElem; pElem=sqliteHashNext(pElem)){
    Table *pTab = sqliteHashData(pElem);
    if( pTab->tnum==iFrom ){
      pTab->tnum = iTo;
    }
  }
  pHash = &pDb->pSchema->idxHash;
  for(pElem=sqliteHashFirst(pHash); pElem; pElem=sqliteHashNext(pElem)){
    Index *pIdx = sqliteHashData(pElem);
    if( pIdx->tnum==iFrom ){
      pIdx->tnum = iTo;
    }
  }
}
#endif

/*
** Write code to erase the table with root-page iTable from database iDb.
** Also write code to modify the sqlite_master table and internal schema
** if a root-page of another table is moved by the btree-layer whilst
** erasing iTable (this can happen with an auto-vacuum database).
*/
static void destroyRootPage(Parse *pParse, int iTable, int iDb){
  Vdbe *v = sqlite3GetVdbe(pParse);
  int r1 = sqlite3GetTempReg(pParse);
  if( iTable<2 ) sqlite3ErrorMsg(pParse, "corrupt schema");
  sqlite3VdbeAddOp3(v, OP_Destroy, iTable, r1, iDb);
  sqlite3MayAbort(pParse);
#ifndef SQLITE_OMIT_AUTOVACUUM
  /* OP_Destroy stores an in integer r1. If this integer
  ** is non-zero, then it is the root page number of a table moved to
  ** location iTable. The following code modifies the sqlite_master table to
  ** reflect this.
  **
  ** The "#NNN" in the SQL is a special constant that means whatever value
  ** is in register NNN.  See grammar rules associated with the TK_REGISTER
  ** token for additional information.
  */
  sqlite3NestedParse(pParse,
     "UPDATE %Q.%s SET rootpage=%d WHERE #%d AND rootpage=#%d",
     pParse->db->aDb[iDb].zDbSName, MASTER_NAME, iTable, r1, r1);
#endif
  sqlite3ReleaseTempReg(pParse, r1);
}

/*
** Write VDBE code to erase table pTab and all associated indices on disk.
** Code to update the sqlite_master tables and internal schema definitions
** in case a root-page belonging to another table is moved by the btree layer
** is also added (this can happen with an auto-vacuum database).
*/
static void destroyTable(Parse *pParse, Table *pTab){
  /* If the database may be auto-vacuum capable (if SQLITE_OMIT_AUTOVACUUM
  ** is not defined), then it is important to call OP_Destroy on the
  ** table and index root-pages in order, starting with the numerically
  ** largest root-page number. This guarantees that none of the root-pages
  ** to be destroyed is relocated by an earlier OP_Destroy. i.e. if the
  ** following were coded:
  **
  ** OP_Destroy 4 0
  ** ...
  ** OP_Destroy 5 0
  **
  ** and root page 5 happened to be the largest root-page number in the
  ** database, then root page 5 would be moved to page 4 by the
  ** "OP_Destroy 4 0" opcode. The subsequent "OP_Destroy 5 0" would hit
  ** a free-list page.
  */
  int iTab = pTab->tnum;
  int iDestroyed = 0;

  while( 1 ){
    Index *pIdx;
    int iLargest = 0;

    if( iDestroyed==0 || iTab<iDestroyed ){
      iLargest = iTab;
    }
    for(pIdx=pTab->pIndex; pIdx; pIdx=pIdx->pNext){
      int iIdx = pIdx->tnum;
      assert( pIdx->pSchema==pTab->pSchema );
      if( (iDestroyed==0 || (iIdx<iDestroyed)) && iIdx>iLargest ){
        iLargest = iIdx;
      }
    }
    if( iLargest==0 ){
      return;
    }else{
      int iDb = sqlite3SchemaToIndex(pParse->db, pTab->pSchema);
      assert( iDb>=0 && iDb<pParse->db->nDb );
      destroyRootPage(pParse, iLargest, iDb);
      iDestroyed = iLargest;
    }
  }
}

/*
** Remove entries from the sqlite_statN tables (for N in (1,2,3))
** after a DROP INDEX or DROP TABLE command.
*/
static void sqlite3ClearStatTables(
  Parse *pParse,         /* The parsing context */
  int iDb,               /* The database number */
  const char *zType,     /* "idx" or "tbl" */
  const char *zName      /* Name of index or table */
){
  int i;
  const char *zDbName = pParse->db->aDb[iDb].zDbSName;
  for(i=1; i<=4; i++){
    char zTab[24];
    sqlite3_snprintf(sizeof(zTab),zTab,"sqlite_stat%d",i);
    if( sqlite3FindTable(pParse->db, zTab, zDbName) ){
      sqlite3NestedParse(pParse,
        "DELETE FROM %Q.%s WHERE %s=%Q",
        zDbName, zTab, zType, zName
      );
    }
  }
}

/*
** Generate code to drop a table.
*/
void sqlite3CodeDropTable(Parse *pParse, Table *pTab, int iDb, int isView){
  Vdbe *v;
  sqlite3 *db = pParse->db;
  Trigger *pTrigger;
  Db *pDb = &db->aDb[iDb];

  v = sqlite3GetVdbe(pParse);
  assert( v!=0 );
  sqlite3BeginWriteOperation(pParse, 1, iDb);

#ifndef SQLITE_OMIT_VIRTUALTABLE
  if( IsVirtual(pTab) ){
    sqlite3VdbeAddOp0(v, OP_VBegin);
  }
#endif

  /* Drop all triggers associated with the table being dropped. Code
  ** is generated to remove entries from sqlite_master and/or
  ** sqlite_temp_master if required.
  */
  pTrigger = sqlite3TriggerList(pParse, pTab);
  while( pTrigger ){
    assert( pTrigger->pSchema==pTab->pSchema ||
        pTrigger->pSchema==db->aDb[1].pSchema );
    sqlite3DropTriggerPtr(pParse, pTrigger);
    pTrigger = pTrigger->pNext;
  }

#ifndef SQLITE_OMIT_AUTOINCREMENT
  /* Remove any entries of the sqlite_sequence table associated with
  ** the table being dropped. This is done before the table is dropped
  ** at the btree level, in case the sqlite_sequence table needs to
  ** move as a result of the drop (can happen in auto-vacuum mode).
  */
  if( pTab->tabFlags & TF_Autoincrement ){
    sqlite3NestedParse(pParse,
      "DELETE FROM %Q.sqlite_sequence WHERE name=%Q",
      pDb->zDbSName, pTab->zName
    );
  }
#endif

  /* Drop all SQLITE_MASTER table and index entries that refer to the
  ** table. The program name loops through the master table and deletes
  ** every row that refers to a table of the same name as the one being
  ** dropped. Triggers are handled separately because a trigger can be
  ** created in the temp database that refers to a table in another
  ** database.
  */
  sqlite3NestedParse(pParse,
      "DELETE FROM %Q.%s WHERE tbl_name=%Q and type!='trigger'",
      pDb->zDbSName, MASTER_NAME, pTab->zName);
  if( !isView && !IsVirtual(pTab) ){
    destroyTable(pParse, pTab);
  }

  /* Remove the table entry from SQLite's internal schema and modify
  ** the schema cookie.
  */
  if( IsVirtual(pTab) ){
    sqlite3VdbeAddOp4(v, OP_VDestroy, iDb, 0, 0, pTab->zName, 0);
    sqlite3MayAbort(pParse);
  }
  sqlite3VdbeAddOp4(v, OP_DropTable, iDb, 0, 0, pTab->zName, 0);
  sqlite3ChangeCookie(pParse, iDb);
  sqliteViewResetAll(db, iDb);
}

/*
** This routine is called to do the work of a DROP TABLE statement.
** pName is the name of the table to be dropped.
*/
void sqlite3DropTable(Parse *pParse, SrcList *pName, int isView, int noErr){
  Table *pTab;
  Vdbe *v;
  sqlite3 *db = pParse->db;
  int iDb;

  if( db->mallocFailed ){
    goto exit_drop_table;
  }
  assert( pParse->nErr==0 );
  assert( pName->nSrc==1 );
  if( sqlite3ReadSchema(pParse) ) goto exit_drop_table;
  if( noErr ) db->suppressErr++;
  assert( isView==0 || isView==LOCATE_VIEW );
  pTab = sqlite3LocateTableItem(pParse, isView, &pName->a[0]);
  if( noErr ) db->suppressErr--;

  if( pTab==0 ){
    if( noErr ) sqlite3CodeVerifyNamedSchema(pParse, pName->a[0].zDatabase);
    goto exit_drop_table;
  }
  iDb = sqlite3SchemaToIndex(db, pTab->pSchema);
  assert( iDb>=0 && iDb<db->nDb );

  /* If pTab is a virtual table, call ViewGetColumnNames() to ensure
  ** it is initialized.
  */
  if( IsVirtual(pTab) && sqlite3ViewGetColumnNames(pParse, pTab) ){
    goto exit_drop_table;
  }
#ifndef SQLITE_OMIT_AUTHORIZATION
  {
    int code;
    const char *zTab = SCHEMA_TABLE(iDb);
    const char *zDb = db->aDb[iDb].zDbSName;
    const char *zArg2 = 0;
    if( sqlite3AuthCheck(pParse, SQLITE_DELETE, zTab, 0, zDb)){
      goto exit_drop_table;
    }
    if( isView ){
      if( !OMIT_TEMPDB && iDb==1 ){
        code = SQLITE_DROP_TEMP_VIEW;
      }else{
        code = SQLITE_DROP_VIEW;
      }
#ifndef SQLITE_OMIT_VIRTUALTABLE
    }else if( IsVirtual(pTab) ){
      code = SQLITE_DROP_VTABLE;
      zArg2 = sqlite3GetVTable(db, pTab)->pMod->zName;
#endif
    }else{
      if( !OMIT_TEMPDB && iDb==1 ){
        code = SQLITE_DROP_TEMP_TABLE;
      }else{
        code = SQLITE_DROP_TABLE;
      }
    }
    if( sqlite3AuthCheck(pParse, code, pTab->zName, zArg2, zDb) ){
      goto exit_drop_table;
    }
    if( sqlite3AuthCheck(pParse, SQLITE_DELETE, pTab->zName, 0, zDb) ){
      goto exit_drop_table;
    }
  }
#endif
  if( sqlite3StrNICmp(pTab->zName, "sqlite_", 7)==0
    && sqlite3StrNICmp(pTab->zName+7, "stat", 4)!=0
    && sqlite3StrNICmp(pTab->zName+7, "parameters", 10)!=0 ){
    sqlite3ErrorMsg(pParse, "table %s may not be dropped", pTab->zName);
    goto exit_drop_table;
  }

#ifndef SQLITE_OMIT_VIEW
  /* Ensure DROP TABLE is not used on a view, and DROP VIEW is not used
  ** on a table.
  */
  if( isView && pTab->pSelect==0 ){
    sqlite3ErrorMsg(pParse, "use DROP TABLE to delete table %s", pTab->zName);
    goto exit_drop_table;
  }
  if( !isView && pTab->pSelect ){
    sqlite3ErrorMsg(pParse, "use DROP VIEW to delete view %s", pTab->zName);
    goto exit_drop_table;
  }
#endif

  /* Generate code to remove the table from the master table
  ** on disk.
  */
  v = sqlite3GetVdbe(pParse);
  if( v ){
    sqlite3BeginWriteOperation(pParse, 1, iDb);
    if( !isView ){
      sqlite3ClearStatTables(pParse, iDb, "tbl", pTab->zName);
      sqlite3FkDropTable(pParse, pName, pTab);
    }
    sqlite3CodeDropTable(pParse, pTab, iDb, isView);
  }

exit_drop_table:
  sqlite3SrcListDelete(db, pName);
}

/*
** This routine is called to create a new foreign key on the table
** currently under construction.  pFromCol determines which columns
** in the current table point to the foreign key.  If pFromCol==0 then
** connect the key to the last column inserted.  pTo is the name of
** the table referred to (a.k.a the "parent" table).  pToCol is a list
** of tables in the parent pTo table.  flags contains all
** information about the conflict resolution algorithms specified
** in the ON DELETE, ON UPDATE and ON INSERT clauses.
**
** An FKey structure is created and added to the table currently
** under construction in the pParse->pNewTable field.
**
** The foreign key is set for IMMEDIATE processing.  A subsequent call
** to sqlite3DeferForeignKey() might change this to DEFERRED.
*/
void sqlite3CreateForeignKey(
  Parse *pParse,       /* Parsing context */
  ExprList *pFromCol,  /* Columns in this table that point to other table */
  Token *pTo,          /* Name of the other table */
  ExprList *pToCol,    /* Columns in the other table */
  int flags            /* Conflict resolution algorithms. */
){
  sqlite3 *db = pParse->db;
#ifndef SQLITE_OMIT_FOREIGN_KEY
  FKey *pFKey = 0;
  FKey *pNextTo;
  Table *p = pParse->pNewTable;
  int nByte;
  int i;
  int nCol;
  char *z;

  assert( pTo!=0 );
  if( p==0 || IN_DECLARE_VTAB ) goto fk_end;
  if( pFromCol==0 ){
    int iCol = p->nCol-1;
    if( NEVER(iCol<0) ) goto fk_end;
    if( pToCol && pToCol->nExpr!=1 ){
      sqlite3ErrorMsg(pParse, "foreign key on %s"
         " should reference only one column of table %T",
         p->aCol[iCol].zName, pTo);
      goto fk_end;
    }
    nCol = 1;
  }else if( pToCol && pToCol->nExpr!=pFromCol->nExpr ){
    sqlite3ErrorMsg(pParse,
        "number of columns in foreign key does not match the number of "
        "columns in the referenced table");
    goto fk_end;
  }else{
    nCol = pFromCol->nExpr;
  }
  nByte = sizeof(*pFKey) + (nCol-1)*sizeof(pFKey->aCol[0]) + pTo->n + 1;
  if( pToCol ){
    for(i=0; i<pToCol->nExpr; i++){
      nByte += sqlite3Strlen30(pToCol->a[i].zName) + 1;
    }
  }
  pFKey = sqlite3DbMallocZero(db, nByte );
  if( pFKey==0 ){
    goto fk_end;
  }
  pFKey->pFrom = p;
  pFKey->pNextFrom = p->pFKey;
  z = (char*)&pFKey->aCol[nCol];
  pFKey->zTo = z;
  if( IN_RENAME_OBJECT ){
    sqlite3RenameTokenMap(pParse, (void*)z, pTo);
  }
  memcpy(z, pTo->z, pTo->n);
  z[pTo->n] = 0;
  sqlite3Dequote(z);
  z += pTo->n+1;
  pFKey->nCol = nCol;
  if( pFromCol==0 ){
    pFKey->aCol[0].iFrom = p->nCol-1;
  }else{
    for(i=0; i<nCol; i++){
      int j;
      for(j=0; j<p->nCol; j++){
        if( sqlite3StrICmp(p->aCol[j].zName, pFromCol->a[i].zName)==0 ){
          pFKey->aCol[i].iFrom = j;
          break;
        }
      }
      if( j>=p->nCol ){
        sqlite3ErrorMsg(pParse,
          "unknown column \"%s\" in foreign key definition",
          pFromCol->a[i].zName);
        goto fk_end;
      }
      if( IN_RENAME_OBJECT ){
        sqlite3RenameTokenRemap(pParse, &pFKey->aCol[i], pFromCol->a[i].zName);
      }
    }
  }
  if( pToCol ){
    for(i=0; i<nCol; i++){
      int n = sqlite3Strlen30(pToCol->a[i].zName);
      pFKey->aCol[i].zCol = z;
      if( IN_RENAME_OBJECT ){
        sqlite3RenameTokenRemap(pParse, z, pToCol->a[i].zName);
      }
      memcpy(z, pToCol->a[i].zName, n);
      z[n] = 0;
      z += n+1;
    }
  }
  pFKey->isDeferred = 0;
  pFKey->aAction[0] = (u8)(flags & 0xff);            /* ON DELETE action */
  pFKey->aAction[1] = (u8)((flags >> 8 ) & 0xff);    /* ON UPDATE action */

  assert( sqlite3SchemaMutexHeld(db, 0, p->pSchema) );
  pNextTo = (FKey *)sqlite3HashInsert(&p->pSchema->fkeyHash,
      pFKey->zTo, (void *)pFKey
  );
  if( pNextTo==pFKey ){
    sqlite3OomFault(db);
    goto fk_end;
  }
  if( pNextTo ){
    assert( pNextTo->pPrevTo==0 );
    pFKey->pNextTo = pNextTo;
    pNextTo->pPrevTo = pFKey;
  }

  /* Link the foreign key to the table as the last step.
  */
  p->pFKey = pFKey;
  pFKey = 0;

fk_end:
  sqlite3DbFree(db, pFKey);
#endif /* !defined(SQLITE_OMIT_FOREIGN_KEY) */
  sqlite3ExprListDelete(db, pFromCol);
  sqlite3ExprListDelete(db, pToCol);
}

/*
** This routine is called when an INITIALLY IMMEDIATE or INITIALLY DEFERRED
** clause is seen as part of a foreign key definition.  The isDeferred
** parameter is 1 for INITIALLY DEFERRED and 0 for INITIALLY IMMEDIATE.
** The behavior of the most recently created foreign key is adjusted
** accordingly.
*/
void sqlite3DeferForeignKey(Parse *pParse, int isDeferred){
#ifndef SQLITE_OMIT_FOREIGN_KEY
  Table *pTab;
  FKey *pFKey;
  if( (pTab = pParse->pNewTable)==0 || (pFKey = pTab->pFKey)==0 ) return;
  assert( isDeferred==0 || isDeferred==1 ); /* EV: R-30323-21917 */
  pFKey->isDeferred = (u8)isDeferred;
#endif
}

/*
** Generate code that will erase and refill index *pIdx.  This is
** used to initialize a newly created index or to recompute the
** content of an index in response to a REINDEX command.
**
** if memRootPage is not negative, it means that the index is newly
** created.  The register specified by memRootPage contains the
** root page number of the index.  If memRootPage is negative, then
** the index already exists and must be cleared before being refilled and
** the root page number of the index is taken from pIndex->tnum.
*/
static void sqlite3RefillIndex(Parse *pParse, Index *pIndex, int memRootPage){
  Table *pTab = pIndex->pTable;  /* The table that is indexed */
  int iTab = pParse->nTab++;     /* Btree cursor used for pTab */
  int iIdx = pParse->nTab++;     /* Btree cursor used for pIndex */
  int iSorter;                   /* Cursor opened by OpenSorter (if in use) */
  int addr1;                     /* Address of top of loop */
  int addr2;                     /* Address to jump to for next iteration */
  int tnum;                      /* Root page of index */
  int iPartIdxLabel;             /* Jump to this label to skip a row */
  Vdbe *v;                       /* Generate code into this virtual machine */
  KeyInfo *pKey;                 /* KeyInfo for index */
  int regRecord;                 /* Register holding assembled index record */
  sqlite3 *db = pParse->db;      /* The database connection */
  int iDb = sqlite3SchemaToIndex(db, pIndex->pSchema);

#ifndef SQLITE_OMIT_AUTHORIZATION
  if( sqlite3AuthCheck(pParse, SQLITE_REINDEX, pIndex->zName, 0,
      db->aDb[iDb].zDbSName ) ){
    return;
  }
#endif

  /* Require a write-lock on the table to perform this operation */
  sqlite3TableLock(pParse, iDb, pTab->tnum, 1, pTab->zName);

  v = sqlite3GetVdbe(pParse);
  if( v==0 ) return;
  if( memRootPage>=0 ){
    tnum = memRootPage;
  }else{
    tnum = pIndex->tnum;
  }
  pKey = sqlite3KeyInfoOfIndex(pParse, pIndex);
  assert( pKey!=0 || db->mallocFailed || pParse->nErr );

  /* Open the sorter cursor if we are to use one. */
  iSorter = pParse->nTab++;
  sqlite3VdbeAddOp4(v, OP_SorterOpen, iSorter, 0, pIndex->nKeyCol, (char*)
                    sqlite3KeyInfoRef(pKey), P4_KEYINFO);

  /* Open the table. Loop through all rows of the table, inserting index
  ** records into the sorter. */
  sqlite3OpenTable(pParse, iTab, iDb, pTab, OP_OpenRead);
  addr1 = sqlite3VdbeAddOp2(v, OP_Rewind, iTab, 0); VdbeCoverage(v);
  regRecord = sqlite3GetTempReg(pParse);
  sqlite3MultiWrite(pParse);

  sqlite3GenerateIndexKey(pParse,pIndex,iTab,regRecord,0,&iPartIdxLabel,0,0);
  sqlite3VdbeAddOp2(v, OP_SorterInsert, iSorter, regRecord);
  sqlite3ResolvePartIdxLabel(pParse, iPartIdxLabel);
  sqlite3VdbeAddOp2(v, OP_Next, iTab, addr1+1); VdbeCoverage(v);
  sqlite3VdbeJumpHere(v, addr1);
  if( memRootPage<0 ) sqlite3VdbeAddOp2(v, OP_Clear, tnum, iDb);
  sqlite3VdbeAddOp4(v, OP_OpenWrite, iIdx, tnum, iDb,
                    (char *)pKey, P4_KEYINFO);
  sqlite3VdbeChangeP5(v, OPFLAG_BULKCSR|((memRootPage>=0)?OPFLAG_P2ISREG:0));

  addr1 = sqlite3VdbeAddOp2(v, OP_SorterSort, iSorter, 0); VdbeCoverage(v);
  if( IsUniqueIndex(pIndex) ){
    int j2 = sqlite3VdbeGoto(v, 1);
    addr2 = sqlite3VdbeCurrentAddr(v);
    sqlite3VdbeVerifyAbortable(v, OE_Abort);
    sqlite3VdbeAddOp4Int(v, OP_SorterCompare, iSorter, j2, regRecord,
                         pIndex->nKeyCol); VdbeCoverage(v);
    sqlite3UniqueConstraint(pParse, OE_Abort, pIndex);
    sqlite3VdbeJumpHere(v, j2);
  }else{
    /* Most CREATE INDEX and REINDEX statements that are not UNIQUE can not
    ** abort. The exception is if one of the indexed expressions contains a
    ** user function that throws an exception when it is evaluated. But the
    ** overhead of adding a statement journal to a CREATE INDEX statement is
    ** very small (since most of the pages written do not contain content that
    ** needs to be restored if the statement aborts), so we call
    ** sqlite3MayAbort() for all CREATE INDEX statements.  */
    sqlite3MayAbort(pParse);
    addr2 = sqlite3VdbeCurrentAddr(v);
  }
  sqlite3VdbeAddOp3(v, OP_SorterData, iSorter, regRecord, iIdx);
  if( !pIndex->bAscKeyBug ){
    /* This OP_SeekEnd opcode makes index insert for a REINDEX go much
    ** faster by avoiding unnecessary seeks.  But the optimization does
    ** not work for UNIQUE constraint indexes on WITHOUT ROWID tables
    ** with DESC primary keys, since those indexes have there keys in
    ** a different order from the main table.
    ** See ticket: https://www.sqlite.org/src/info/bba7b69f9849b5bf
    */
    sqlite3VdbeAddOp1(v, OP_SeekEnd, iIdx);
  }
  sqlite3VdbeAddOp2(v, OP_IdxInsert, iIdx, regRecord);
  sqlite3VdbeChangeP5(v, OPFLAG_USESEEKRESULT);
  sqlite3ReleaseTempReg(pParse, regRecord);
  sqlite3VdbeAddOp2(v, OP_SorterNext, iSorter, addr2); VdbeCoverage(v);
  sqlite3VdbeJumpHere(v, addr1);

  sqlite3VdbeAddOp1(v, OP_Close, iTab);
  sqlite3VdbeAddOp1(v, OP_Close, iIdx);
  sqlite3VdbeAddOp1(v, OP_Close, iSorter);
}

/*
** Allocate heap space to hold an Index object with nCol columns.
**
** Increase the allocation size to provide an extra nExtra bytes
** of 8-byte aligned space after the Index object and return a
** pointer to this extra space in *ppExtra.
*/
Index *sqlite3AllocateIndexObject(
  sqlite3 *db,         /* Database connection */
  i16 nCol,            /* Total number of columns in the index */
  int nExtra,          /* Number of bytes of extra space to alloc */
  char **ppExtra       /* Pointer to the "extra" space */
){
  Index *p;            /* Allocated index object */
  int nByte;           /* Bytes of space for Index object + arrays */

  nByte = ROUND8(sizeof(Index)) +              /* Index structure  */
          ROUND8(sizeof(char*)*nCol) +         /* Index.azColl     */
          ROUND8(sizeof(LogEst)*(nCol+1) +     /* Index.aiRowLogEst   */
                 sizeof(i16)*nCol +            /* Index.aiColumn   */
                 sizeof(u8)*nCol);             /* Index.aSortOrder */
  p = sqlite3DbMallocZero(db, nByte + nExtra);
  if( p ){
    char *pExtra = ((char*)p)+ROUND8(sizeof(Index));
    p->azColl = (const char**)pExtra; pExtra += ROUND8(sizeof(char*)*nCol);
    p->aiRowLogEst = (LogEst*)pExtra; pExtra += sizeof(LogEst)*(nCol+1);
    p->aiColumn = (i16*)pExtra;       pExtra += sizeof(i16)*nCol;
    p->aSortOrder = (u8*)pExtra;
    p->nColumn = nCol;
    p->nKeyCol = nCol - 1;
    *ppExtra = ((char*)p) + nByte;
  }
  return p;
}

/*
** If expression list pList contains an expression that was parsed with
** an explicit "NULLS FIRST" or "NULLS LAST" clause, leave an error in
** pParse and return non-zero. Otherwise, return zero.
*/
int sqlite3HasExplicitNulls(Parse *pParse, ExprList *pList){
  if( pList ){
    int i;
    for(i=0; i<pList->nExpr; i++){
      if( pList->a[i].bNulls ){
        u8 sf = pList->a[i].sortFlags;
        sqlite3ErrorMsg(pParse, "unsupported use of NULLS %s",
            (sf==0 || sf==3) ? "FIRST" : "LAST"
        );
        return 1;
      }
    }
  }
  return 0;
}

/*
** Create a new index for an SQL table.  pName1.pName2 is the name of the index
** and pTblList is the name of the table that is to be indexed.  Both will
** be NULL for a primary key or an index that is created to satisfy a
** UNIQUE constraint.  If pTable and pIndex are NULL, use pParse->pNewTable
** as the table to be indexed.  pParse->pNewTable is a table that is
** currently being constructed by a CREATE TABLE statement.
**
** pList is a list of columns to be indexed.  pList will be NULL if this
** is a primary key or unique-constraint on the most recent column added
** to the table currently under construction.
*/
void sqlite3CreateIndex(
  Parse *pParse,     /* All information about this parse */
  Token *pName1,     /* First part of index name. May be NULL */
  Token *pName2,     /* Second part of index name. May be NULL */
  SrcList *pTblName, /* Table to index. Use pParse->pNewTable if 0 */
  ExprList *pList,   /* A list of columns to be indexed */
  int onError,       /* OE_Abort, OE_Ignore, OE_Replace, or OE_None */
  Token *pStart,     /* The CREATE token that begins this statement */
  Expr *pPIWhere,    /* WHERE clause for partial indices */
  int sortOrder,     /* Sort order of primary key when pList==NULL */
  int ifNotExist,    /* Omit error if index already exists */
  u8 idxType         /* The index type */
){
  Table *pTab = 0;     /* Table to be indexed */
  Index *pIndex = 0;   /* The index to be created */
  char *zName = 0;     /* Name of the index */
  int nName;           /* Number of characters in zName */
  int i, j;
  DbFixer sFix;        /* For assigning database names to pTable */
  int sortOrderMask;   /* 1 to honor DESC in index.  0 to ignore. */
  sqlite3 *db = pParse->db;
  Db *pDb;             /* The specific table containing the indexed database */
  int iDb;             /* Index of the database that is being written */
  Token *pName = 0;    /* Unqualified name of the index to create */
  struct ExprList_item *pListItem; /* For looping over pList */
  int nExtra = 0;                  /* Space allocated for zExtra[] */
  int nExtraCol;                   /* Number of extra columns needed */
  char *zExtra = 0;                /* Extra space after the Index object */
  Index *pPk = 0;      /* PRIMARY KEY index for WITHOUT ROWID tables */

  if( db->mallocFailed || pParse->nErr>0 ){
    goto exit_create_index;
  }
  if( IN_DECLARE_VTAB && idxType!=SQLITE_IDXTYPE_PRIMARYKEY ){
    goto exit_create_index;
  }
  if( SQLITE_OK!=sqlite3ReadSchema(pParse) ){
    goto exit_create_index;
  }
  if( sqlite3HasExplicitNulls(pParse, pList) ){
    goto exit_create_index;
  }

  /*
  ** Find the table that is to be indexed.  Return early if not found.
  */
  if( pTblName!=0 ){

    /* Use the two-part index name to determine the database
    ** to search for the table. 'Fix' the table name to this db
    ** before looking up the table.
    */
    assert( pName1 && pName2 );
    iDb = sqlite3TwoPartName(pParse, pName1, pName2, &pName);
    if( iDb<0 ) goto exit_create_index;
    assert( pName && pName->z );

#ifndef SQLITE_OMIT_TEMPDB
    /* If the index name was unqualified, check if the table
    ** is a temp table. If so, set the database to 1. Do not do this
    ** if initialising a database schema.
    */
    if( !db->init.busy ){
      pTab = sqlite3SrcListLookup(pParse, pTblName);
      if( pName2->n==0 && pTab && pTab->pSchema==db->aDb[1].pSchema ){
        iDb = 1;
      }
    }
#endif

    sqlite3FixInit(&sFix, pParse, iDb, "index", pName);
    if( sqlite3FixSrcList(&sFix, pTblName) ){
      /* Because the parser constructs pTblName from a single identifier,
      ** sqlite3FixSrcList can never fail. */
      assert(0);
    }
    pTab = sqlite3LocateTableItem(pParse, 0, &pTblName->a[0]);
    assert( db->mallocFailed==0 || pTab==0 );
    if( pTab==0 ) goto exit_create_index;
    if( iDb==1 && db->aDb[iDb].pSchema!=pTab->pSchema ){
      sqlite3ErrorMsg(pParse,
           "cannot create a TEMP index on non-TEMP table \"%s\"",
           pTab->zName);
      goto exit_create_index;
    }
    if( !HasRowid(pTab) ) pPk = sqlite3PrimaryKeyIndex(pTab);
  }else{
    assert( pName==0 );
    assert( pStart==0 );
    pTab = pParse->pNewTable;
    if( !pTab ) goto exit_create_index;
    iDb = sqlite3SchemaToIndex(db, pTab->pSchema);
  }
  pDb = &db->aDb[iDb];

  assert( pTab!=0 );
  assert( pParse->nErr==0 );
  if( sqlite3StrNICmp(pTab->zName, "sqlite_", 7)==0
       && db->init.busy==0
       && pTblName!=0
#if SQLITE_USER_AUTHENTICATION
       && sqlite3UserAuthTable(pTab->zName)==0
#endif
#ifdef SQLITE_ALLOW_SQLITE_MASTER_INDEX
       && sqlite3StrICmp(&pTab->zName[7],"master")!=0
#endif
 ){
    sqlite3ErrorMsg(pParse, "table %s may not be indexed", pTab->zName);
    goto exit_create_index;
  }
#ifndef SQLITE_OMIT_VIEW
  if( pTab->pSelect ){
    sqlite3ErrorMsg(pParse, "views may not be indexed");
    goto exit_create_index;
  }
#endif
#ifndef SQLITE_OMIT_VIRTUALTABLE
  if( IsVirtual(pTab) ){
    sqlite3ErrorMsg(pParse, "virtual tables may not be indexed");
    goto exit_create_index;
  }
#endif

  /*
  ** Find the name of the index.  Make sure there is not already another
  ** index or table with the same name.
  **
  ** Exception:  If we are reading the names of permanent indices from the
  ** sqlite_master table (because some other process changed the schema) and
  ** one of the index names collides with the name of a temporary table or
  ** index, then we will continue to process this index.
  **
  ** If pName==0 it means that we are
  ** dealing with a primary key or UNIQUE constraint.  We have to invent our
  ** own name.
  */
  if( pName ){
    zName = sqlite3NameFromToken(db, pName);
    if( zName==0 ) goto exit_create_index;
    assert( pName->z!=0 );
    if( SQLITE_OK!=sqlite3CheckObjectName(pParse, zName,"index",pTab->zName) ){
      goto exit_create_index;
    }
    if( !IN_RENAME_OBJECT ){
      if( !db->init.busy ){
        if( sqlite3FindTable(db, zName, 0)!=0 ){
          sqlite3ErrorMsg(pParse, "there is already a table named %s", zName);
          goto exit_create_index;
        }
      }
      if( sqlite3FindIndex(db, zName, pDb->zDbSName)!=0 ){
        if( !ifNotExist ){
          sqlite3ErrorMsg(pParse, "index %s already exists", zName);
        }else{
          assert( !db->init.busy );
          sqlite3CodeVerifySchema(pParse, iDb);
        }
        goto exit_create_index;
      }
    }
  }else{
    int n;
    Index *pLoop;
    for(pLoop=pTab->pIndex, n=1; pLoop; pLoop=pLoop->pNext, n++){}
    zName = sqlite3MPrintf(db, "sqlite_autoindex_%s_%d", pTab->zName, n);
    if( zName==0 ){
      goto exit_create_index;
    }

    /* Automatic index names generated from within sqlite3_declare_vtab()
    ** must have names that are distinct from normal automatic index names.
    ** The following statement converts "sqlite3_autoindex..." into
    ** "sqlite3_butoindex..." in order to make the names distinct.
    ** The "vtab_err.test" test demonstrates the need of this statement. */
    if( IN_SPECIAL_PARSE ) zName[7]++;
  }

  /* Check for authorization to create an index.
  */
#ifndef SQLITE_OMIT_AUTHORIZATION
  if( !IN_RENAME_OBJECT ){
    const char *zDb = pDb->zDbSName;
    if( sqlite3AuthCheck(pParse, SQLITE_INSERT, SCHEMA_TABLE(iDb), 0, zDb) ){
      goto exit_create_index;
    }
    i = SQLITE_CREATE_INDEX;
    if( !OMIT_TEMPDB && iDb==1 ) i = SQLITE_CREATE_TEMP_INDEX;
    if( sqlite3AuthCheck(pParse, i, zName, pTab->zName, zDb) ){
      goto exit_create_index;
    }
  }
#endif

  /* If pList==0, it means this routine was called to make a primary
  ** key out of the last column added to the table under construction.
  ** So create a fake list to simulate this.
  */
  if( pList==0 ){
    Token prevCol;
    Column *pCol = &pTab->aCol[pTab->nCol-1];
    pCol->colFlags |= COLFLAG_UNIQUE;
    sqlite3TokenInit(&prevCol, pCol->zName);
    pList = sqlite3ExprListAppend(pParse, 0,
              sqlite3ExprAlloc(db, TK_ID, &prevCol, 0));
    if( pList==0 ) goto exit_create_index;
    assert( pList->nExpr==1 );
    sqlite3ExprListSetSortOrder(pList, sortOrder, SQLITE_SO_UNDEFINED);
  }else{
    sqlite3ExprListCheckLength(pParse, pList, "index");
    if( pParse->nErr ) goto exit_create_index;
  }

  /* Figure out how many bytes of space are required to store explicitly
  ** specified collation sequence names.
  */
  for(i=0; i<pList->nExpr; i++){
    Expr *pExpr = pList->a[i].pExpr;
    assert( pExpr!=0 );
    if( pExpr->op==TK_COLLATE ){
      nExtra += (1 + sqlite3Strlen30(pExpr->u.zToken));
    }
  }

  /*
  ** Allocate the index structure.
  */
  nName = sqlite3Strlen30(zName);
  nExtraCol = pPk ? pPk->nKeyCol : 1;
  assert( pList->nExpr + nExtraCol <= 32767 /* Fits in i16 */ );
  pIndex = sqlite3AllocateIndexObject(db, pList->nExpr + nExtraCol,
                                      nName + nExtra + 1, &zExtra);
  if( db->mallocFailed ){
    goto exit_create_index;
  }
  assert( EIGHT_BYTE_ALIGNMENT(pIndex->aiRowLogEst) );
  assert( EIGHT_BYTE_ALIGNMENT(pIndex->azColl) );
  pIndex->zName = zExtra;
  zExtra += nName + 1;
  memcpy(pIndex->zName, zName, nName+1);
  pIndex->pTable = pTab;
  pIndex->onError = (u8)onError;
  pIndex->uniqNotNull = onError!=OE_None;
  pIndex->idxType = idxType;
  pIndex->pSchema = db->aDb[iDb].pSchema;
  pIndex->nKeyCol = pList->nExpr;
  if( pPIWhere ){
    sqlite3ResolveSelfReference(pParse, pTab, NC_PartIdx, pPIWhere, 0);
    pIndex->pPartIdxWhere = pPIWhere;
    pPIWhere = 0;
  }
  assert( sqlite3SchemaMutexHeld(db, iDb, 0) );

  /* Check to see if we should honor DESC requests on index columns
  */
  if( pDb->pSchema->file_format>=4 ){
    sortOrderMask = -1;   /* Honor DESC */
  }else{
    sortOrderMask = 0;    /* Ignore DESC */
  }

  /* Analyze the list of expressions that form the terms of the index and
  ** report any errors.  In the common case where the expression is exactly
  ** a table column, store that column in aiColumn[].  For general expressions,
  ** populate pIndex->aColExpr and store XN_EXPR (-2) in aiColumn[].
  **
  ** TODO: Issue a warning if two or more columns of the index are identical.
  ** TODO: Issue a warning if the table primary key is used as part of the
  ** index key.
  */
  pListItem = pList->a;
  if( IN_RENAME_OBJECT ){
    pIndex->aColExpr = pList;
    pList = 0;
  }
  for(i=0; i<pIndex->nKeyCol; i++, pListItem++){
    Expr *pCExpr;                  /* The i-th index expression */
    int requestedSortOrder;        /* ASC or DESC on the i-th expression */
    const char *zColl;             /* Collation sequence name */

    sqlite3StringToId(pListItem->pExpr);
    sqlite3ResolveSelfReference(pParse, pTab, NC_IdxExpr, pListItem->pExpr, 0);
    if( pParse->nErr ) goto exit_create_index;
    pCExpr = sqlite3ExprSkipCollate(pListItem->pExpr);
    if( pCExpr->op!=TK_COLUMN ){
      if( pTab==pParse->pNewTable ){
        sqlite3ErrorMsg(pParse, "expressions prohibited in PRIMARY KEY and "
                                "UNIQUE constraints");
        goto exit_create_index;
      }
      if( pIndex->aColExpr==0 ){
        pIndex->aColExpr = pList;
        pList = 0;
      }
      j = XN_EXPR;
      pIndex->aiColumn[i] = XN_EXPR;
      pIndex->uniqNotNull = 0;
    }else{
      j = pCExpr->iColumn;
      assert( j<=0x7fff );
      if( j<0 ){
        j = pTab->iPKey;
      }else if( pTab->aCol[j].notNull==0 ){
        pIndex->uniqNotNull = 0;
      }
      pIndex->aiColumn[i] = (i16)j;
    }
    zColl = 0;
    if( pListItem->pExpr->op==TK_COLLATE ){
      int nColl;
      zColl = pListItem->pExpr->u.zToken;
      nColl = sqlite3Strlen30(zColl) + 1;
      assert( nExtra>=nColl );
      memcpy(zExtra, zColl, nColl);
      zColl = zExtra;
      zExtra += nColl;
      nExtra -= nColl;
    }else if( j>=0 ){
      zColl = pTab->aCol[j].zColl;
    }
    if( !zColl ) zColl = sqlite3StrBINARY;
    if( !db->init.busy && !sqlite3LocateCollSeq(pParse, zColl) ){
      goto exit_create_index;
    }
    pIndex->azColl[i] = zColl;
    requestedSortOrder = pListItem->sortFlags & sortOrderMask;
    pIndex->aSortOrder[i] = (u8)requestedSortOrder;
  }

  /* Append the table key to the end of the index.  For WITHOUT ROWID
  ** tables (when pPk!=0) this will be the declared PRIMARY KEY.  For
  ** normal tables (when pPk==0) this will be the rowid.
  */
  if( pPk ){
    for(j=0; j<pPk->nKeyCol; j++){
      int x = pPk->aiColumn[j];
      assert( x>=0 );
      if( isDupColumn(pIndex, pIndex->nKeyCol, pPk, j) ){
        pIndex->nColumn--;
      }else{
        testcase( hasColumn(pIndex->aiColumn,pIndex->nKeyCol,x) );
        pIndex->aiColumn[i] = x;
        pIndex->azColl[i] = pPk->azColl[j];
        pIndex->aSortOrder[i] = pPk->aSortOrder[j];
        i++;
      }
    }
    assert( i==pIndex->nColumn );
  }else{
    pIndex->aiColumn[i] = XN_ROWID;
    pIndex->azColl[i] = sqlite3StrBINARY;
  }
  sqlite3DefaultRowEst(pIndex);
  if( pParse->pNewTable==0 ) estimateIndexWidth(pIndex);

  /* If this index contains every column of its table, then mark
  ** it as a covering index */
  assert( HasRowid(pTab)
      || pTab->iPKey<0 || sqlite3ColumnOfIndex(pIndex, pTab->iPKey)>=0 );
  recomputeColumnsNotIndexed(pIndex);
  if( pTblName!=0 && pIndex->nColumn>=pTab->nCol ){
    pIndex->isCovering = 1;
    for(j=0; j<pTab->nCol; j++){
      if( j==pTab->iPKey ) continue;
      if( sqlite3ColumnOfIndex(pIndex,j)>=0 ) continue;
      pIndex->isCovering = 0;
      break;
    }
  }

  if( pTab==pParse->pNewTable ){
    /* This routine has been called to create an automatic index as a
    ** result of a PRIMARY KEY or UNIQUE clause on a column definition, or
    ** a PRIMARY KEY or UNIQUE clause following the column definitions.
    ** i.e. one of:
    **
    ** CREATE TABLE t(x PRIMARY KEY, y);
    ** CREATE TABLE t(x, y, UNIQUE(x, y));
    **
    ** Either way, check to see if the table already has such an index. If
    ** so, don't bother creating this one. This only applies to
    ** automatically created indices. Users can do as they wish with
    ** explicit indices.
    **
    ** Two UNIQUE or PRIMARY KEY constraints are considered equivalent
    ** (and thus suppressing the second one) even if they have different
    ** sort orders.
    **
    ** If there are different collating sequences or if the columns of
    ** the constraint occur in different orders, then the constraints are
    ** considered distinct and both result in separate indices.
    */
    Index *pIdx;
    for(pIdx=pTab->pIndex; pIdx; pIdx=pIdx->pNext){
      int k;
      assert( IsUniqueIndex(pIdx) );
      assert( pIdx->idxType!=SQLITE_IDXTYPE_APPDEF );
      assert( IsUniqueIndex(pIndex) );

      if( pIdx->nKeyCol!=pIndex->nKeyCol ) continue;
      for(k=0; k<pIdx->nKeyCol; k++){
        const char *z1;
        const char *z2;
        assert( pIdx->aiColumn[k]>=0 );
        if( pIdx->aiColumn[k]!=pIndex->aiColumn[k] ) break;
        z1 = pIdx->azColl[k];
        z2 = pIndex->azColl[k];
        if( sqlite3StrICmp(z1, z2) ) break;
      }
      if( k==pIdx->nKeyCol ){
        if( pIdx->onError!=pIndex->onError ){
          /* This constraint creates the same index as a previous
          ** constraint specified somewhere in the CREATE TABLE statement.
          ** However the ON CONFLICT clauses are different. If both this
          ** constraint and the previous equivalent constraint have explicit
          ** ON CONFLICT clauses this is an error. Otherwise, use the
          ** explicitly specified behavior for the index.
          */
          if( !(pIdx->onError==OE_Default || pIndex->onError==OE_Default) ){
            sqlite3ErrorMsg(pParse,
                "conflicting ON CONFLICT clauses specified", 0);
          }
          if( pIdx->onError==OE_Default ){
            pIdx->onError = pIndex->onError;
          }
        }
        if( idxType==SQLITE_IDXTYPE_PRIMARYKEY ) pIdx->idxType = idxType;
        if( IN_RENAME_OBJECT ){
          pIndex->pNext = pParse->pNewIndex;
          pParse->pNewIndex = pIndex;
          pIndex = 0;
        }
        goto exit_create_index;
      }
    }
  }

  if( !IN_RENAME_OBJECT ){

    /* Link the new Index structure to its table and to the other
    ** in-memory database structures.
    */
    assert( pParse->nErr==0 );
    if( db->init.busy ){
      Index *p;
      assert( !IN_SPECIAL_PARSE );
      assert( sqlite3SchemaMutexHeld(db, 0, pIndex->pSchema) );
      if( pTblName!=0 ){
        pIndex->tnum = db->init.newTnum;
        if( sqlite3IndexHasDuplicateRootPage(pIndex) ){
          sqlite3ErrorMsg(pParse, "invalid rootpage");
          pParse->rc = SQLITE_CORRUPT_BKPT;
          goto exit_create_index;
        }
      }
      p = sqlite3HashInsert(&pIndex->pSchema->idxHash,
          pIndex->zName, pIndex);
      if( p ){
        assert( p==pIndex );  /* Malloc must have failed */
        sqlite3OomFault(db);
        goto exit_create_index;
      }
      db->mDbFlags |= DBFLAG_SchemaChange;
    }

    /* If this is the initial CREATE INDEX statement (or CREATE TABLE if the
    ** index is an implied index for a UNIQUE or PRIMARY KEY constraint) then
    ** emit code to allocate the index rootpage on disk and make an entry for
    ** the index in the sqlite_master table and populate the index with
    ** content.  But, do not do this if we are simply reading the sqlite_master
    ** table to parse the schema, or if this index is the PRIMARY KEY index
    ** of a WITHOUT ROWID table.
    **
    ** If pTblName==0 it means this index is generated as an implied PRIMARY KEY
    ** or UNIQUE index in a CREATE TABLE statement.  Since the table
    ** has just been created, it contains no data and the index initialization
    ** step can be skipped.
    */
    else if( HasRowid(pTab) || pTblName!=0 ){
      Vdbe *v;
      char *zStmt;
      int iMem = ++pParse->nMem;

      v = sqlite3GetVdbe(pParse);
      if( v==0 ) goto exit_create_index;

      sqlite3BeginWriteOperation(pParse, 1, iDb);

      /* Create the rootpage for the index using CreateIndex. But before
      ** doing so, code a Noop instruction and store its address in
      ** Index.tnum. This is required in case this index is actually a
      ** PRIMARY KEY and the table is actually a WITHOUT ROWID table. In
      ** that case the convertToWithoutRowidTable() routine will replace
      ** the Noop with a Goto to jump over the VDBE code generated below. */
      pIndex->tnum = sqlite3VdbeAddOp0(v, OP_Noop);
      sqlite3VdbeAddOp3(v, OP_CreateBtree, iDb, iMem, BTREE_BLOBKEY);

      /* Gather the complete text of the CREATE INDEX statement into
      ** the zStmt variable
      */
      assert( pName!=0 || pStart==0 );
      if( pStart ){
        int n = (int)(pParse->sLastToken.z - pName->z) + pParse->sLastToken.n;
        if( pName->z[n-1]==';' ) n--;
        /* A named index with an explicit CREATE INDEX statement */
        zStmt = sqlite3MPrintf(db, "CREATE%s INDEX %.*s",
            onError==OE_None ? "" : " UNIQUE", n, pName->z);
      }else{
        /* An automatic index created by a PRIMARY KEY or UNIQUE constraint */
        /* zStmt = sqlite3MPrintf(""); */
        zStmt = 0;
      }

      /* Add an entry in sqlite_master for this index
      */
      sqlite3NestedParse(pParse,
          "INSERT INTO %Q.%s VALUES('index',%Q,%Q,#%d,%Q);",
          db->aDb[iDb].zDbSName, MASTER_NAME,
          pIndex->zName,
          pTab->zName,
          iMem,
          zStmt
          );
      sqlite3DbFree(db, zStmt);

      /* Fill the index with data and reparse the schema. Code an OP_Expire
      ** to invalidate all pre-compiled statements.
      */
      if( pTblName ){
        sqlite3RefillIndex(pParse, pIndex, iMem);
        sqlite3ChangeCookie(pParse, iDb);
        sqlite3VdbeAddParseSchemaOp(v, iDb,
            sqlite3MPrintf(db, "name='%q' AND type='index'", pIndex->zName));
        sqlite3VdbeAddOp2(v, OP_Expire, 0, 1);
      }

      sqlite3VdbeJumpHere(v, pIndex->tnum);
    }
  }

  /* When adding an index to the list of indices for a table, make
  ** sure all indices labeled OE_Replace come after all those labeled
  ** OE_Ignore.  This is necessary for the correct constraint check
  ** processing (in sqlite3GenerateConstraintChecks()) as part of
  ** UPDATE and INSERT statements.
  */
  if( db->init.busy || pTblName==0 ){
    if( onError!=OE_Replace || pTab->pIndex==0
         || pTab->pIndex->onError==OE_Replace){
      pIndex->pNext = pTab->pIndex;
      pTab->pIndex = pIndex;
    }else{
      Index *pOther = pTab->pIndex;
      while( pOther->pNext && pOther->pNext->onError!=OE_Replace ){
        pOther = pOther->pNext;
      }
      pIndex->pNext = pOther->pNext;
      pOther->pNext = pIndex;
    }
    pIndex = 0;
  }
  else if( IN_RENAME_OBJECT ){
    assert( pParse->pNewIndex==0 );
    pParse->pNewIndex = pIndex;
    pIndex = 0;
  }

  /* Clean up before exiting */
exit_create_index:
  if( pIndex ) sqlite3FreeIndex(db, pIndex);
  sqlite3ExprDelete(db, pPIWhere);
  sqlite3ExprListDelete(db, pList);
  sqlite3SrcListDelete(db, pTblName);
  sqlite3DbFree(db, zName);
}

/*
** Fill the Index.aiRowEst[] array with default information - information
** to be used when we have not run the ANALYZE command.
**
** aiRowEst[0] is supposed to contain the number of elements in the index.
** Since we do not know, guess 1 million.  aiRowEst[1] is an estimate of the
** number of rows in the table that match any particular value of the
** first column of the index.  aiRowEst[2] is an estimate of the number
** of rows that match any particular combination of the first 2 columns
** of the index.  And so forth.  It must always be the case that
*
**           aiRowEst[N]<=aiRowEst[N-1]
**           aiRowEst[N]>=1
**
** Apart from that, we have little to go on besides intuition as to
** how aiRowEst[] should be initialized.  The numbers generated here
** are based on typical values found in actual indices.
*/
void sqlite3DefaultRowEst(Index *pIdx){
  /*                10,  9,  8,  7,  6 */
  LogEst aVal[] = { 33, 32, 30, 28, 26 };
  LogEst *a = pIdx->aiRowLogEst;
  int nCopy = MIN(ArraySize(aVal), pIdx->nKeyCol);
  int i;

  /* Indexes with default row estimates should not have stat1 data */
  assert( !pIdx->hasStat1 );

  /* Set the first entry (number of rows in the index) to the estimated
  ** number of rows in the table, or half the number of rows in the table
  ** for a partial index.   But do not let the estimate drop below 10. */
  a[0] = pIdx->pTable->nRowLogEst;
  if( pIdx->pPartIdxWhere!=0 ) a[0] -= 10;  assert( 10==sqlite3LogEst(2) );
  if( a[0]<33 ) a[0] = 33;                  assert( 33==sqlite3LogEst(10) );

  /* Estimate that a[1] is 10, a[2] is 9, a[3] is 8, a[4] is 7, a[5] is
  ** 6 and each subsequent value (if any) is 5.  */
  memcpy(&a[1], aVal, nCopy*sizeof(LogEst));
  for(i=nCopy+1; i<=pIdx->nKeyCol; i++){
    a[i] = 23;                    assert( 23==sqlite3LogEst(5) );
  }

  assert( 0==sqlite3LogEst(1) );
  if( IsUniqueIndex(pIdx) ) a[pIdx->nKeyCol] = 0;
}

/*
** This routine will drop an existing named index.  This routine
** implements the DROP INDEX statement.
*/
void sqlite3DropIndex(Parse *pParse, SrcList *pName, int ifExists){
  Index *pIndex;
  Vdbe *v;
  sqlite3 *db = pParse->db;
  int iDb;

  assert( pParse->nErr==0 );   /* Never called with prior errors */
  if( db->mallocFailed ){
    goto exit_drop_index;
  }
  assert( pName->nSrc==1 );
  if( SQLITE_OK!=sqlite3ReadSchema(pParse) ){
    goto exit_drop_index;
  }
  pIndex = sqlite3FindIndex(db, pName->a[0].zName, pName->a[0].zDatabase);
  if( pIndex==0 ){
    if( !ifExists ){
      sqlite3ErrorMsg(pParse, "no such index: %S", pName, 0);
    }else{
      sqlite3CodeVerifyNamedSchema(pParse, pName->a[0].zDatabase);
    }
    pParse->checkSchema = 1;
    goto exit_drop_index;
  }
  if( pIndex->idxType!=SQLITE_IDXTYPE_APPDEF ){
    sqlite3ErrorMsg(pParse, "index associated with UNIQUE "
      "or PRIMARY KEY constraint cannot be dropped", 0);
    goto exit_drop_index;
  }
  iDb = sqlite3SchemaToIndex(db, pIndex->pSchema);
#ifndef SQLITE_OMIT_AUTHORIZATION
  {
    int code = SQLITE_DROP_INDEX;
    Table *pTab = pIndex->pTable;
    const char *zDb = db->aDb[iDb].zDbSName;
    const char *zTab = SCHEMA_TABLE(iDb);
    if( sqlite3AuthCheck(pParse, SQLITE_DELETE, zTab, 0, zDb) ){
      goto exit_drop_index;
    }
    if( !OMIT_TEMPDB && iDb ) code = SQLITE_DROP_TEMP_INDEX;
    if( sqlite3AuthCheck(pParse, code, pIndex->zName, pTab->zName, zDb) ){
      goto exit_drop_index;
    }
  }
#endif

  /* Generate code to remove the index and from the master table */
  v = sqlite3GetVdbe(pParse);
  if( v ){
    sqlite3BeginWriteOperation(pParse, 1, iDb);
    sqlite3NestedParse(pParse,
       "DELETE FROM %Q.%s WHERE name=%Q AND type='index'",
       db->aDb[iDb].zDbSName, MASTER_NAME, pIndex->zName
    );
    sqlite3ClearStatTables(pParse, iDb, "idx", pIndex->zName);
    sqlite3ChangeCookie(pParse, iDb);
    destroyRootPage(pParse, pIndex->tnum, iDb);
    sqlite3VdbeAddOp4(v, OP_DropIndex, iDb, 0, 0, pIndex->zName, 0);
  }

exit_drop_index:
  sqlite3SrcListDelete(db, pName);
}

/*
** pArray is a pointer to an array of objects. Each object in the
** array is szEntry bytes in size. This routine uses sqlite3DbRealloc()
** to extend the array so that there is space for a new object at the end.
**
** When this function is called, *pnEntry contains the current size of
** the array (in entries - so the allocation is ((*pnEntry) * szEntry) bytes
** in total).
**
** If the realloc() is successful (i.e. if no OOM condition occurs), the
** space allocated for the new object is zeroed, *pnEntry updated to
** reflect the new size of the array and a pointer to the new allocation
** returned. *pIdx is set to the index of the new array entry in this case.
**
** Otherwise, if the realloc() fails, *pIdx is set to -1, *pnEntry remains
** unchanged and a copy of pArray returned.
*/
void *sqlite3ArrayAllocate(
  sqlite3 *db,      /* Connection to notify of malloc failures */
  void *pArray,     /* Array of objects.  Might be reallocated */
  int szEntry,      /* Size of each object in the array */
  int *pnEntry,     /* Number of objects currently in use */
  int *pIdx         /* Write the index of a new slot here */
){
  char *z;
  sqlite3_int64 n = *pIdx = *pnEntry;
  if( (n & (n-1))==0 ){
    sqlite3_int64 sz = (n==0) ? 1 : 2*n;
    void *pNew = sqlite3DbRealloc(db, pArray, sz*szEntry);
    if( pNew==0 ){
      *pIdx = -1;
      return pArray;
    }
    pArray = pNew;
  }
  z = (char*)pArray;
  memset(&z[n * szEntry], 0, szEntry);
  ++*pnEntry;
  return pArray;
}

/*
** Append a new element to the given IdList.  Create a new IdList if
** need be.
**
** A new IdList is returned, or NULL if malloc() fails.
*/
IdList *sqlite3IdListAppend(Parse *pParse, IdList *pList, Token *pToken){
  sqlite3 *db = pParse->db;
  int i;
  if( pList==0 ){
    pList = sqlite3DbMallocZero(db, sizeof(IdList) );
    if( pList==0 ) return 0;
  }
  pList->a = sqlite3ArrayAllocate(
      db,
      pList->a,
      sizeof(pList->a[0]),
      &pList->nId,
      &i
  );
  if( i<0 ){
    sqlite3IdListDelete(db, pList);
    return 0;
  }
  pList->a[i].zName = sqlite3NameFromToken(db, pToken);
  if( IN_RENAME_OBJECT && pList->a[i].zName ){
    sqlite3RenameTokenMap(pParse, (void*)pList->a[i].zName, pToken);
  }
  return pList;
}

/*
** Delete an IdList.
*/
void sqlite3IdListDelete(sqlite3 *db, IdList *pList){
  int i;
  if( pList==0 ) return;
  for(i=0; i<pList->nId; i++){
    sqlite3DbFree(db, pList->a[i].zName);
  }
  sqlite3DbFree(db, pList->a);
  sqlite3DbFreeNN(db, pList);
}

/*
** Return the index in pList of the identifier named zId.  Return -1
** if not found.
*/
int sqlite3IdListIndex(IdList *pList, const char *zName){
  int i;
  if( pList==0 ) return -1;
  for(i=0; i<pList->nId; i++){
    if( sqlite3StrICmp(pList->a[i].zName, zName)==0 ) return i;
  }
  return -1;
}

/*
** Maximum size of a SrcList object.
** The SrcList object is used to represent the FROM clause of a
** SELECT statement, and the query planner cannot deal with more
** than 64 tables in a join.  So any value larger than 64 here
** is sufficient for most uses.  Smaller values, like say 10, are
** appropriate for small and memory-limited applications.
*/
#ifndef SQLITE_MAX_SRCLIST
# define SQLITE_MAX_SRCLIST 200
#endif

/*
** Expand the space allocated for the given SrcList object by
** creating nExtra new slots beginning at iStart.  iStart is zero based.
** New slots are zeroed.
**
** For example, suppose a SrcList initially contains two entries: A,B.
** To append 3 new entries onto the end, do this:
**
**    sqlite3SrcListEnlarge(db, pSrclist, 3, 2);
**
** After the call above it would contain:  A, B, nil, nil, nil.
** If the iStart argument had been 1 instead of 2, then the result
** would have been:  A, nil, nil, nil, B.  To prepend the new slots,
** the iStart value would be 0.  The result then would
** be: nil, nil, nil, A, B.
**
** If a memory allocation fails or the SrcList becomes too large, leave
** the original SrcList unchanged, return NULL, and leave an error message
** in pParse.
*/
SrcList *sqlite3SrcListEnlarge(
  Parse *pParse,     /* Parsing context into which errors are reported */
  SrcList *pSrc,     /* The SrcList to be enlarged */
  int nExtra,        /* Number of new slots to add to pSrc->a[] */
  int iStart         /* Index in pSrc->a[] of first new slot */
){
  int i;

  /* Sanity checking on calling parameters */
  assert( iStart>=0 );
  assert( nExtra>=1 );
  assert( pSrc!=0 );
  assert( iStart<=pSrc->nSrc );

  /* Allocate additional space if needed */
  if( (u32)pSrc->nSrc+nExtra>pSrc->nAlloc ){
    SrcList *pNew;
    sqlite3_int64 nAlloc = 2*(sqlite3_int64)pSrc->nSrc+nExtra;
    sqlite3 *db = pParse->db;

    if( pSrc->nSrc+nExtra>=SQLITE_MAX_SRCLIST ){
      sqlite3ErrorMsg(pParse, "too many FROM clause terms, max: %d",
                      SQLITE_MAX_SRCLIST);
      return 0;
    }
    if( nAlloc>SQLITE_MAX_SRCLIST ) nAlloc = SQLITE_MAX_SRCLIST;
    pNew = sqlite3DbRealloc(db, pSrc,
               sizeof(*pSrc) + (nAlloc-1)*sizeof(pSrc->a[0]) );
    if( pNew==0 ){
      assert( db->mallocFailed );
      return 0;
    }
    pSrc = pNew;
    pSrc->nAlloc = nAlloc;
  }

  /* Move existing slots that come after the newly inserted slots
  ** out of the way */
  for(i=pSrc->nSrc-1; i>=iStart; i--){
    pSrc->a[i+nExtra] = pSrc->a[i];
  }
  pSrc->nSrc += nExtra;

  /* Zero the newly allocated slots */
  memset(&pSrc->a[iStart], 0, sizeof(pSrc->a[0])*nExtra);
  for(i=iStart; i<iStart+nExtra; i++){
    pSrc->a[i].iCursor = -1;
  }

  /* Return a pointer to the enlarged SrcList */
  return pSrc;
}


/*
** Append a new table name to the given SrcList.  Create a new SrcList if
** need be.  A new entry is created in the SrcList even if pTable is NULL.
**
** A SrcList is returned, or NULL if there is an OOM error or if the
** SrcList grows to large.  The returned
** SrcList might be the same as the SrcList that was input or it might be
** a new one.  If an OOM error does occurs, then the prior value of pList
** that is input to this routine is automatically freed.
**
** If pDatabase is not null, it means that the table has an optional
** database name prefix.  Like this:  "database.table".  The pDatabase
** points to the table name and the pTable points to the database name.
** The SrcList.a[].zName field is filled with the table name which might
** come from pTable (if pDatabase is NULL) or from pDatabase.
** SrcList.a[].zDatabase is filled with the database name from pTable,
** or with NULL if no database is specified.
**
** In other words, if call like this:
**
**         sqlite3SrcListAppend(D,A,B,0);
**
** Then B is a table name and the database name is unspecified.  If called
** like this:
**
**         sqlite3SrcListAppend(D,A,B,C);
**
** Then C is the table name and B is the database name.  If C is defined
** then so is B.  In other words, we never have a case where:
**
**         sqlite3SrcListAppend(D,A,0,C);
**
** Both pTable and pDatabase are assumed to be quoted.  They are dequoted
** before being added to the SrcList.
*/
SrcList *sqlite3SrcListAppend(
  Parse *pParse,      /* Parsing context, in which errors are reported */
  SrcList *pList,     /* Append to this SrcList. NULL creates a new SrcList */
  Token *pTable,      /* Table to append */
  Token *pDatabase    /* Database of the table */
){
  struct SrcList_item *pItem;
  sqlite3 *db;
  assert( pDatabase==0 || pTable!=0 );  /* Cannot have C without B */
  assert( pParse!=0 );
  assert( pParse->db!=0 );
  db = pParse->db;
  if( pList==0 ){
    pList = sqlite3DbMallocRawNN(pParse->db, sizeof(SrcList) );
    if( pList==0 ) return 0;
    pList->nAlloc = 1;
    pList->nSrc = 1;
    memset(&pList->a[0], 0, sizeof(pList->a[0]));
    pList->a[0].iCursor = -1;
  }else{
    SrcList *pNew = sqlite3SrcListEnlarge(pParse, pList, 1, pList->nSrc);
    if( pNew==0 ){
      sqlite3SrcListDelete(db, pList);
      return 0;
    }else{
      pList = pNew;
    }
  }
  pItem = &pList->a[pList->nSrc-1];
  if( pDatabase && pDatabase->z==0 ){
    pDatabase = 0;
  }
  if( pDatabase ){
    pItem->zName = sqlite3NameFromToken(db, pDatabase);
    pItem->zDatabase = sqlite3NameFromToken(db, pTable);
  }else{
    pItem->zName = sqlite3NameFromToken(db, pTable);
    pItem->zDatabase = 0;
  }
  return pList;
}

/*
** Assign VdbeCursor index numbers to all tables in a SrcList
*/
void sqlite3SrcListAssignCursors(Parse *pParse, SrcList *pList){
  int i;
  struct SrcList_item *pItem;
  assert(pList || pParse->db->mallocFailed );
  if( pList ){
    for(i=0, pItem=pList->a; i<pList->nSrc; i++, pItem++){
      if( pItem->iCursor>=0 ) break;
      pItem->iCursor = pParse->nTab++;
      if( pItem->pSelect ){
        sqlite3SrcListAssignCursors(pParse, pItem->pSelect->pSrc);
      }
    }
  }
}

/*
** Delete an entire SrcList including all its substructure.
*/
void sqlite3SrcListDelete(sqlite3 *db, SrcList *pList){
  int i;
  struct SrcList_item *pItem;
  if( pList==0 ) return;
  for(pItem=pList->a, i=0; i<pList->nSrc; i++, pItem++){
    sqlite3DbFree(db, pItem->zDatabase);
    sqlite3DbFree(db, pItem->zName);
    sqlite3DbFree(db, pItem->zAlias);
    if( pItem->fg.isIndexedBy ) sqlite3DbFree(db, pItem->u1.zIndexedBy);
    if( pItem->fg.isTabFunc ) sqlite3ExprListDelete(db, pItem->u1.pFuncArg);
    sqlite3DeleteTable(db, pItem->pTab);
    sqlite3SelectDelete(db, pItem->pSelect);
    sqlite3ExprDelete(db, pItem->pOn);
    sqlite3IdListDelete(db, pItem->pUsing);
  }
  sqlite3DbFreeNN(db, pList);
}

/*
** This routine is called by the parser to add a new term to the
** end of a growing FROM clause.  The "p" parameter is the part of
** the FROM clause that has already been constructed.  "p" is NULL
** if this is the first term of the FROM clause.  pTable and pDatabase
** are the name of the table and database named in the FROM clause term.
** pDatabase is NULL if the database name qualifier is missing - the
** usual case.  If the term has an alias, then pAlias points to the
** alias token.  If the term is a subquery, then pSubquery is the
** SELECT statement that the subquery encodes.  The pTable and
** pDatabase parameters are NULL for subqueries.  The pOn and pUsing
** parameters are the content of the ON and USING clauses.
**
** Return a new SrcList which encodes is the FROM with the new
** term added.
*/
SrcList *sqlite3SrcListAppendFromTerm(
  Parse *pParse,          /* Parsing context */
  SrcList *p,             /* The left part of the FROM clause already seen */
  Token *pTable,          /* Name of the table to add to the FROM clause */
  Token *pDatabase,       /* Name of the database containing pTable */
  Token *pAlias,          /* The right-hand side of the AS subexpression */
  Select *pSubquery,      /* A subquery used in place of a table name */
  Expr *pOn,              /* The ON clause of a join */
  IdList *pUsing          /* The USING clause of a join */
){
  struct SrcList_item *pItem;
  sqlite3 *db = pParse->db;
  if( !p && (pOn || pUsing) ){
    sqlite3ErrorMsg(pParse, "a JOIN clause is required before %s",
      (pOn ? "ON" : "USING")
    );
    goto append_from_error;
  }
  p = sqlite3SrcListAppend(pParse, p, pTable, pDatabase);
  if( p==0 ){
    goto append_from_error;
  }
  assert( p->nSrc>0 );
  pItem = &p->a[p->nSrc-1];
  assert( (pTable==0)==(pDatabase==0) );
  assert( pItem->zName==0 || pDatabase!=0 );
  if( IN_RENAME_OBJECT && pItem->zName ){
    Token *pToken = (ALWAYS(pDatabase) && pDatabase->z) ? pDatabase : pTable;
    sqlite3RenameTokenMap(pParse, pItem->zName, pToken);
  }
  assert( pAlias!=0 );
  if( pAlias->n ){
    pItem->zAlias = sqlite3NameFromToken(db, pAlias);
  }
  pItem->pSelect = pSubquery;
  pItem->pOn = pOn;
  pItem->pUsing = pUsing;
  return p;

 append_from_error:
  assert( p==0 );
  sqlite3ExprDelete(db, pOn);
  sqlite3IdListDelete(db, pUsing);
  sqlite3SelectDelete(db, pSubquery);
  return 0;
}

/*
** Add an INDEXED BY or NOT INDEXED clause to the most recently added
** element of the source-list passed as the second argument.
*/
void sqlite3SrcListIndexedBy(Parse *pParse, SrcList *p, Token *pIndexedBy){
  assert( pIndexedBy!=0 );
  if( p && pIndexedBy->n>0 ){
    struct SrcList_item *pItem;
    assert( p->nSrc>0 );
    pItem = &p->a[p->nSrc-1];
    assert( pItem->fg.notIndexed==0 );
    assert( pItem->fg.isIndexedBy==0 );
    assert( pItem->fg.isTabFunc==0 );
    if( pIndexedBy->n==1 && !pIndexedBy->z ){
      /* A "NOT INDEXED" clause was supplied. See parse.y
      ** construct "indexed_opt" for details. */
      pItem->fg.notIndexed = 1;
    }else{
      pItem->u1.zIndexedBy = sqlite3NameFromToken(pParse->db, pIndexedBy);
      pItem->fg.isIndexedBy = 1;
    }
  }
}

/*
** Add the list of function arguments to the SrcList entry for a
** table-valued-function.
*/
void sqlite3SrcListFuncArgs(Parse *pParse, SrcList *p, ExprList *pList){
  if( p ){
    struct SrcList_item *pItem = &p->a[p->nSrc-1];
    assert( pItem->fg.notIndexed==0 );
    assert( pItem->fg.isIndexedBy==0 );
    assert( pItem->fg.isTabFunc==0 );
    pItem->u1.pFuncArg = pList;
    pItem->fg.isTabFunc = 1;
  }else{
    sqlite3ExprListDelete(pParse->db, pList);
  }
}

/*
** When building up a FROM clause in the parser, the join operator
** is initially attached to the left operand.  But the code generator
** expects the join operator to be on the right operand.  This routine
** Shifts all join operators from left to right for an entire FROM
** clause.
**
** Example: Suppose the join is like this:
**
**           A natural cross join B
**
** The operator is "natural cross join".  The A and B operands are stored
** in p->a[0] and p->a[1], respectively.  The parser initially stores the
** operator with A.  This routine shifts that operator over to B.
*/
void sqlite3SrcListShiftJoinType(SrcList *p){
  if( p ){
    int i;
    for(i=p->nSrc-1; i>0; i--){
      p->a[i].fg.jointype = p->a[i-1].fg.jointype;
    }
    p->a[0].fg.jointype = 0;
  }
}

/*
** Generate VDBE code for a BEGIN statement.
*/
void sqlite3BeginTransaction(Parse *pParse, int type){
  sqlite3 *db;
  Vdbe *v;
  int i;

  assert( pParse!=0 );
  db = pParse->db;
  assert( db!=0 );
  if( sqlite3AuthCheck(pParse, SQLITE_TRANSACTION, "BEGIN", 0, 0) ){
    return;
  }
  v = sqlite3GetVdbe(pParse);
  if( !v ) return;
  if( type!=TK_DEFERRED ){
    for(i=0; i<db->nDb; i++){
      sqlite3VdbeAddOp2(v, OP_Transaction, i, (type==TK_EXCLUSIVE)+1);
      sqlite3VdbeUsesBtree(v, i);
    }
  }
  sqlite3VdbeAddOp0(v, OP_AutoCommit);
}

/*
** Generate VDBE code for a COMMIT or ROLLBACK statement.
** Code for ROLLBACK is generated if eType==TK_ROLLBACK.  Otherwise
** code is generated for a COMMIT.
*/
void sqlite3EndTransaction(Parse *pParse, int eType){
  Vdbe *v;
  int isRollback;

  assert( pParse!=0 );
  assert( pParse->db!=0 );
  assert( eType==TK_COMMIT || eType==TK_END || eType==TK_ROLLBACK );
  isRollback = eType==TK_ROLLBACK;
  if( sqlite3AuthCheck(pParse, SQLITE_TRANSACTION,
       isRollback ? "ROLLBACK" : "COMMIT", 0, 0) ){
    return;
  }
  v = sqlite3GetVdbe(pParse);
  if( v ){
    sqlite3VdbeAddOp2(v, OP_AutoCommit, 1, isRollback);
  }
}

/*
** This function is called by the parser when it parses a command to create,
** release or rollback an SQL savepoint.
*/
void sqlite3Savepoint(Parse *pParse, int op, Token *pName){
  char *zName = sqlite3NameFromToken(pParse->db, pName);
  if( zName ){
    Vdbe *v = sqlite3GetVdbe(pParse);
#ifndef SQLITE_OMIT_AUTHORIZATION
    static const char * const az[] = { "BEGIN", "RELEASE", "ROLLBACK" };
    assert( !SAVEPOINT_BEGIN && SAVEPOINT_RELEASE==1 && SAVEPOINT_ROLLBACK==2 );
#endif
    if( !v || sqlite3AuthCheck(pParse, SQLITE_SAVEPOINT, az[op], zName, 0) ){
      sqlite3DbFree(pParse->db, zName);
      return;
    }
    sqlite3VdbeAddOp4(v, OP_Savepoint, op, 0, 0, zName, P4_DYNAMIC);
  }
}

/*
** Make sure the TEMP database is open and available for use.  Return
** the number of errors.  Leave any error messages in the pParse structure.
*/
int sqlite3OpenTempDatabase(Parse *pParse){
  sqlite3 *db = pParse->db;
  if( db->aDb[1].pBt==0 && !pParse->explain ){
    int rc;
    Btree *pBt;
    static const int flags =
          SQLITE_OPEN_READWRITE |
          SQLITE_OPEN_CREATE |
          SQLITE_OPEN_EXCLUSIVE |
          SQLITE_OPEN_DELETEONCLOSE |
          SQLITE_OPEN_TEMP_DB;

    rc = sqlite3BtreeOpen(db->pVfs, 0, db, &pBt, 0, flags);
    if( rc!=SQLITE_OK ){
      sqlite3ErrorMsg(pParse, "unable to open a temporary database "
        "file for storing temporary tables");
      pParse->rc = rc;
      return 1;
    }
    db->aDb[1].pBt = pBt;
    assert( db->aDb[1].pSchema );
    if( SQLITE_NOMEM==sqlite3BtreeSetPageSize(pBt, db->nextPagesize, -1, 0) ){
      sqlite3OomFault(db);
      return 1;
    }
  }
  return 0;
}

/*
** Record the fact that the schema cookie will need to be verified
** for database iDb.  The code to actually verify the schema cookie
** will occur at the end of the top-level VDBE and will be generated
** later, by sqlite3FinishCoding().
*/
void sqlite3CodeVerifySchema(Parse *pParse, int iDb){
  Parse *pToplevel = sqlite3ParseToplevel(pParse);

  assert( iDb>=0 && iDb<pParse->db->nDb );
  assert( pParse->db->aDb[iDb].pBt!=0 || iDb==1 );
  assert( iDb<SQLITE_MAX_ATTACHED+2 );
  assert( sqlite3SchemaMutexHeld(pParse->db, iDb, 0) );
  if( DbMaskTest(pToplevel->cookieMask, iDb)==0 ){
    DbMaskSet(pToplevel->cookieMask, iDb);
    if( !OMIT_TEMPDB && iDb==1 ){
      sqlite3OpenTempDatabase(pToplevel);
    }
  }
}

/*
** If argument zDb is NULL, then call sqlite3CodeVerifySchema() for each
** attached database. Otherwise, invoke it for the database named zDb only.
*/
void sqlite3CodeVerifyNamedSchema(Parse *pParse, const char *zDb){
  sqlite3 *db = pParse->db;
  int i;
  for(i=0; i<db->nDb; i++){
    Db *pDb = &db->aDb[i];
    if( pDb->pBt && (!zDb || 0==sqlite3StrICmp(zDb, pDb->zDbSName)) ){
      sqlite3CodeVerifySchema(pParse, i);
    }
  }
}

/*
** Generate VDBE code that prepares for doing an operation that
** might change the database.
**
** This routine starts a new transaction if we are not already within
** a transaction.  If we are already within a transaction, then a checkpoint
** is set if the setStatement parameter is true.  A checkpoint should
** be set for operations that might fail (due to a constraint) part of
** the way through and which will need to undo some writes without having to
** rollback the whole transaction.  For operations where all constraints
** can be checked before any changes are made to the database, it is never
** necessary to undo a write and the checkpoint should not be set.
*/
void sqlite3BeginWriteOperation(Parse *pParse, int setStatement, int iDb){
  Parse *pToplevel = sqlite3ParseToplevel(pParse);
  sqlite3CodeVerifySchema(pParse, iDb);
  DbMaskSet(pToplevel->writeMask, iDb);
  pToplevel->isMultiWrite |= setStatement;
}

/*
** Indicate that the statement currently under construction might write
** more than one entry (example: deleting one row then inserting another,
** inserting multiple rows in a table, or inserting a row and index entries.)
** If an abort occurs after some of these writes have completed, then it will
** be necessary to undo the completed writes.
*/
void sqlite3MultiWrite(Parse *pParse){
  Parse *pToplevel = sqlite3ParseToplevel(pParse);
  pToplevel->isMultiWrite = 1;
}

/*
** The code generator calls this routine if is discovers that it is
** possible to abort a statement prior to completion.  In order to
** perform this abort without corrupting the database, we need to make
** sure that the statement is protected by a statement transaction.
**
** Technically, we only need to set the mayAbort flag if the
** isMultiWrite flag was previously set.  There is a time dependency
** such that the abort must occur after the multiwrite.  This makes
** some statements involving the REPLACE conflict resolution algorithm
** go a little faster.  But taking advantage of this time dependency
** makes it more difficult to prove that the code is correct (in
** particular, it prevents us from writing an effective
** implementation of sqlite3AssertMayAbort()) and so we have chosen
** to take the safe route and skip the optimization.
*/
void sqlite3MayAbort(Parse *pParse){
  Parse *pToplevel = sqlite3ParseToplevel(pParse);
  pToplevel->mayAbort = 1;
}

/*
** Code an OP_Halt that causes the vdbe to return an SQLITE_CONSTRAINT
** error. The onError parameter determines which (if any) of the statement
** and/or current transaction is rolled back.
*/
void sqlite3HaltConstraint(
  Parse *pParse,    /* Parsing context */
  int errCode,      /* extended error code */
  int onError,      /* Constraint type */
  char *p4,         /* Error message */
  i8 p4type,        /* P4_STATIC or P4_TRANSIENT */
  u8 p5Errmsg       /* P5_ErrMsg type */
){
  Vdbe *v = sqlite3GetVdbe(pParse);
  assert( (errCode&0xff)==SQLITE_CONSTRAINT );
  if( onError==OE_Abort ){
    sqlite3MayAbort(pParse);
  }
  sqlite3VdbeAddOp4(v, OP_Halt, errCode, onError, 0, p4, p4type);
  sqlite3VdbeChangeP5(v, p5Errmsg);
}

/*
** Code an OP_Halt due to UNIQUE or PRIMARY KEY constraint violation.
*/
void sqlite3UniqueConstraint(
  Parse *pParse,    /* Parsing context */
  int onError,      /* Constraint type */
  Index *pIdx       /* The index that triggers the constraint */
){
  char *zErr;
  int j;
  StrAccum errMsg;
  Table *pTab = pIdx->pTable;

  sqlite3StrAccumInit(&errMsg, pParse->db, 0, 0,
                      pParse->db->aLimit[SQLITE_LIMIT_LENGTH]);
  if( pIdx->aColExpr ){
    sqlite3_str_appendf(&errMsg, "index '%q'", pIdx->zName);
  }else{
    for(j=0; j<pIdx->nKeyCol; j++){
      char *zCol;
      assert( pIdx->aiColumn[j]>=0 );
      zCol = pTab->aCol[pIdx->aiColumn[j]].zName;
      if( j ) sqlite3_str_append(&errMsg, ", ", 2);
      sqlite3_str_appendall(&errMsg, pTab->zName);
      sqlite3_str_append(&errMsg, ".", 1);
      sqlite3_str_appendall(&errMsg, zCol);
    }
  }
  zErr = sqlite3StrAccumFinish(&errMsg);
  sqlite3HaltConstraint(pParse,
    IsPrimaryKeyIndex(pIdx) ? SQLITE_CONSTRAINT_PRIMARYKEY
                            : SQLITE_CONSTRAINT_UNIQUE,
    onError, zErr, P4_DYNAMIC, P5_ConstraintUnique);
}


/*
** Code an OP_Halt due to non-unique rowid.
*/
void sqlite3RowidConstraint(
  Parse *pParse,    /* Parsing context */
  int onError,      /* Conflict resolution algorithm */
  Table *pTab       /* The table with the non-unique rowid */
){
  char *zMsg;
  int rc;
  if( pTab->iPKey>=0 ){
    zMsg = sqlite3MPrintf(pParse->db, "%s.%s", pTab->zName,
                          pTab->aCol[pTab->iPKey].zName);
    rc = SQLITE_CONSTRAINT_PRIMARYKEY;
  }else{
    zMsg = sqlite3MPrintf(pParse->db, "%s.rowid", pTab->zName);
    rc = SQLITE_CONSTRAINT_ROWID;
  }
  sqlite3HaltConstraint(pParse, rc, onError, zMsg, P4_DYNAMIC,
                        P5_ConstraintUnique);
}

/*
** Check to see if pIndex uses the collating sequence pColl.  Return
** true if it does and false if it does not.
*/
#ifndef SQLITE_OMIT_REINDEX
static int collationMatch(const char *zColl, Index *pIndex){
  int i;
  assert( zColl!=0 );
  for(i=0; i<pIndex->nColumn; i++){
    const char *z = pIndex->azColl[i];
    assert( z!=0 || pIndex->aiColumn[i]<0 );
    if( pIndex->aiColumn[i]>=0 && 0==sqlite3StrICmp(z, zColl) ){
      return 1;
    }
  }
  return 0;
}
#endif

/*
** Recompute all indices of pTab that use the collating sequence pColl.
** If pColl==0 then recompute all indices of pTab.
*/
#ifndef SQLITE_OMIT_REINDEX
static void reindexTable(Parse *pParse, Table *pTab, char const *zColl){
  if( !IsVirtual(pTab) ){
    Index *pIndex;              /* An index associated with pTab */

    for(pIndex=pTab->pIndex; pIndex; pIndex=pIndex->pNext){
      if( zColl==0 || collationMatch(zColl, pIndex) ){
        int iDb = sqlite3SchemaToIndex(pParse->db, pTab->pSchema);
        sqlite3BeginWriteOperation(pParse, 0, iDb);
        sqlite3RefillIndex(pParse, pIndex, -1);
      }
    }
  }
}
#endif

/*
** Recompute all indices of all tables in all databases where the
** indices use the collating sequence pColl.  If pColl==0 then recompute
** all indices everywhere.
*/
#ifndef SQLITE_OMIT_REINDEX
static void reindexDatabases(Parse *pParse, char const *zColl){
  Db *pDb;                    /* A single database */
  int iDb;                    /* The database index number */
  sqlite3 *db = pParse->db;   /* The database connection */
  HashElem *k;                /* For looping over tables in pDb */
  Table *pTab;                /* A table in the database */

  assert( sqlite3BtreeHoldsAllMutexes(db) );  /* Needed for schema access */
  for(iDb=0, pDb=db->aDb; iDb<db->nDb; iDb++, pDb++){
    assert( pDb!=0 );
    for(k=sqliteHashFirst(&pDb->pSchema->tblHash);  k; k=sqliteHashNext(k)){
      pTab = (Table*)sqliteHashData(k);
      reindexTable(pParse, pTab, zColl);
    }
  }
}
#endif

/*
** Generate code for the REINDEX command.
**
**        REINDEX                            -- 1
**        REINDEX  <collation>               -- 2
**        REINDEX  ?<database>.?<tablename>  -- 3
**        REINDEX  ?<database>.?<indexname>  -- 4
**
** Form 1 causes all indices in all attached databases to be rebuilt.
** Form 2 rebuilds all indices in all databases that use the named
** collating function.  Forms 3 and 4 rebuild the named index or all
** indices associated with the named table.
*/
#ifndef SQLITE_OMIT_REINDEX
void sqlite3Reindex(Parse *pParse, Token *pName1, Token *pName2){
  CollSeq *pColl;             /* Collating sequence to be reindexed, or NULL */
  char *z;                    /* Name of a table or index */
  const char *zDb;            /* Name of the database */
  Table *pTab;                /* A table in the database */
  Index *pIndex;              /* An index associated with pTab */
  int iDb;                    /* The database index number */
  sqlite3 *db = pParse->db;   /* The database connection */
  Token *pObjName;            /* Name of the table or index to be reindexed */

  /* Read the database schema. If an error occurs, leave an error message
  ** and code in pParse and return NULL. */
  if( SQLITE_OK!=sqlite3ReadSchema(pParse) ){
    return;
  }

  if( pName1==0 ){
    reindexDatabases(pParse, 0);
    return;
  }else if( NEVER(pName2==0) || pName2->z==0 ){
    char *zColl;
    assert( pName1->z );
    zColl = sqlite3NameFromToken(pParse->db, pName1);
    if( !zColl ) return;
    pColl = sqlite3FindCollSeq(db, ENC(db), zColl, 0);
    if( pColl ){
      reindexDatabases(pParse, zColl);
      sqlite3DbFree(db, zColl);
      return;
    }
    sqlite3DbFree(db, zColl);
  }
  iDb = sqlite3TwoPartName(pParse, pName1, pName2, &pObjName);
  if( iDb<0 ) return;
  z = sqlite3NameFromToken(db, pObjName);
  if( z==0 ) return;
  zDb = db->aDb[iDb].zDbSName;
  pTab = sqlite3FindTable(db, z, zDb);
  if( pTab ){
    reindexTable(pParse, pTab, 0);
    sqlite3DbFree(db, z);
    return;
  }
  pIndex = sqlite3FindIndex(db, z, zDb);
  sqlite3DbFree(db, z);
  if( pIndex ){
    sqlite3BeginWriteOperation(pParse, 0, iDb);
    sqlite3RefillIndex(pParse, pIndex, -1);
    return;
  }
  sqlite3ErrorMsg(pParse, "unable to identify the object to be reindexed");
}
#endif

/*
** Return a KeyInfo structure that is appropriate for the given Index.
**
** The caller should invoke sqlite3KeyInfoUnref() on the returned object
** when it has finished using it.
*/
KeyInfo *sqlite3KeyInfoOfIndex(Parse *pParse, Index *pIdx){
  int i;
  int nCol = pIdx->nColumn;
  int nKey = pIdx->nKeyCol;
  KeyInfo *pKey;
  if( pParse->nErr ) return 0;
  if( pIdx->uniqNotNull ){
    pKey = sqlite3KeyInfoAlloc(pParse->db, nKey, nCol-nKey);
  }else{
    pKey = sqlite3KeyInfoAlloc(pParse->db, nCol, 0);
  }
  if( pKey ){
    assert( sqlite3KeyInfoIsWriteable(pKey) );
    for(i=0; i<nCol; i++){
      const char *zColl = pIdx->azColl[i];
      pKey->aColl[i] = zColl==sqlite3StrBINARY ? 0 :
                        sqlite3LocateCollSeq(pParse, zColl);
      pKey->aSortFlags[i] = pIdx->aSortOrder[i];
      assert( 0==(pKey->aSortFlags[i] & KEYINFO_ORDER_BIGNULL) );
    }
    if( pParse->nErr ){
      assert( pParse->rc==SQLITE_ERROR_MISSING_COLLSEQ );
      if( pIdx->bNoQuery==0 ){
        /* Deactivate the index because it contains an unknown collating
        ** sequence.  The only way to reactive the index is to reload the
        ** schema.  Adding the missing collating sequence later does not
        ** reactive the index.  The application had the chance to register
        ** the missing index using the collation-needed callback.  For
        ** simplicity, SQLite will not give the application a second chance.
        */
        pIdx->bNoQuery = 1;
        pParse->rc = SQLITE_ERROR_RETRY;
      }
      sqlite3KeyInfoUnref(pKey);
      pKey = 0;
    }
  }
  return pKey;
}

#ifndef SQLITE_OMIT_CTE
/*
** This routine is invoked once per CTE by the parser while parsing a
** WITH clause.
*/
With *sqlite3WithAdd(
  Parse *pParse,          /* Parsing context */
  With *pWith,            /* Existing WITH clause, or NULL */
  Token *pName,           /* Name of the common-table */
  ExprList *pArglist,     /* Optional column name list for the table */
  Select *pQuery          /* Query used to initialize the table */
){
  sqlite3 *db = pParse->db;
  With *pNew;
  char *zName;

  /* Check that the CTE name is unique within this WITH clause. If
  ** not, store an error in the Parse structure. */
  zName = sqlite3NameFromToken(pParse->db, pName);
  if( zName && pWith ){
    int i;
    for(i=0; i<pWith->nCte; i++){
      if( sqlite3StrICmp(zName, pWith->a[i].zName)==0 ){
        sqlite3ErrorMsg(pParse, "duplicate WITH table name: %s", zName);
      }
    }
  }

  if( pWith ){
    sqlite3_int64 nByte = sizeof(*pWith) + (sizeof(pWith->a[1]) * pWith->nCte);
    pNew = sqlite3DbRealloc(db, pWith, nByte);
  }else{
    pNew = sqlite3DbMallocZero(db, sizeof(*pWith));
  }
  assert( (pNew!=0 && zName!=0) || db->mallocFailed );

  if( db->mallocFailed ){
    sqlite3ExprListDelete(db, pArglist);
    sqlite3SelectDelete(db, pQuery);
    sqlite3DbFree(db, zName);
    pNew = pWith;
  }else{
    pNew->a[pNew->nCte].pSelect = pQuery;
    pNew->a[pNew->nCte].pCols = pArglist;
    pNew->a[pNew->nCte].zName = zName;
    pNew->a[pNew->nCte].zCteErr = 0;
    pNew->nCte++;
  }

  return pNew;
}

/*
** Free the contents of the With object passed as the second argument.
*/
void sqlite3WithDelete(sqlite3 *db, With *pWith){
  if( pWith ){
    int i;
    for(i=0; i<pWith->nCte; i++){
      struct Cte *pCte = &pWith->a[i];
      sqlite3ExprListDelete(db, pCte->pCols);
      sqlite3SelectDelete(db, pCte->pSelect);
      sqlite3DbFree(db, pCte->zName);
    }
    sqlite3DbFree(db, pWith);
  }
}
#endif /* !defined(SQLITE_OMIT_CTE) */