/*

** 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 parser

** to handle INSERT statements in SQLite.

**

** $Id: insert.cpp 1282 2008-11-13 09:31:33Z LarsPson $

*/

#include "sqliteInt.h"

/*

** Set P3 of the most recently inserted opcode to a column affinity

** string for index pIdx. A column affinity string has one character

** for each column in the table, according to the affinity of the column:

**

**  Character      Column affinity

**  ------------------------------

**  'a'            TEXT

**  'b'            NONE

**  'c'            NUMERIC

**  'd'            INTEGER

**  'e'            REAL

*/

void sqlite3IndexAffinityStr(Vdbe *v, Index *pIdx){

  if( !pIdx->zColAff ){

    /* The first time a column affinity string for a particular index is

    ** required, it is allocated and populated here. It is then stored as

    ** a member of the Index structure for subsequent use.

    **

    ** The column affinity string will eventually be deleted by

    ** sqliteDeleteIndex() when the Index structure itself is cleaned

    ** up.

    */

    int n;

    Table *pTab = pIdx->pTable;

    sqlite3 *db = sqlite3VdbeDb(v);

    pIdx->zColAff = (char *)sqlite3DbMallocZero(db, pIdx->nColumn+1);

    if( !pIdx->zColAff ){

      return;

    }

    for(n=0; n<pIdx->nColumn; n++){

      pIdx->zColAff[n] = pTab->aCol[pIdx->aiColumn[n]].affinity;

    }

    pIdx->zColAff[pIdx->nColumn] = '\0';

  }

  sqlite3VdbeChangeP3(v, -1, pIdx->zColAff, 0);

}

/*

** Set P3 of the most recently inserted opcode to a column affinity

** string for table pTab. A column affinity string has one character

** for each column indexed by the index, according to the affinity of the

** column:

**

**  Character      Column affinity

**  ------------------------------

**  'a'            TEXT

**  'b'            NONE

**  'c'            NUMERIC

**  'd'            INTEGER

**  'e'            REAL

*/

void sqlite3TableAffinityStr(Vdbe *v, Table *pTab){

  /* The first time a column affinity string for a particular table

  ** is required, it is allocated and populated here. It is then 

  ** stored as a member of the Table structure for subsequent use.

  **

  ** The column affinity string will eventually be deleted by

  ** sqlite3DeleteTable() when the Table structure itself is cleaned up.

  */

  if( !pTab->zColAff ){

    char *zColAff;

    int i;

    sqlite3 *db = sqlite3VdbeDb(v);

    zColAff = (char *)sqlite3DbMallocZero(db, pTab->nCol+1);

    if( !zColAff ){

      return;

    }

    for(i=0; i<pTab->nCol; i++){

      zColAff[i] = pTab->aCol[i].affinity;

    }

    zColAff[pTab->nCol] = '\0';

    pTab->zColAff = zColAff;

  }

  sqlite3VdbeChangeP3(v, -1, pTab->zColAff, 0);

}

/*

** Return non-zero if the table pTab in database iDb or any of its indices

** have been opened at any point in the VDBE program beginning at location

** iStartAddr throught the end of the program.  This is used to see if 

** a statement of the form  "INSERT INTO <iDb, pTab> SELECT ..." can 

** run without using temporary table for the results of the SELECT. 

*/

static int readsTable(Vdbe *v, int iStartAddr, int iDb, Table *pTab){

  int i;

  int iEnd = sqlite3VdbeCurrentAddr(v);

  for(i=iStartAddr; i<iEnd; i++){

    VdbeOp *pOp = sqlite3VdbeGetOp(v, i);

    assert( pOp!=0 );

    if( pOp->opcode==OP_OpenRead ){

      VdbeOp *pPrior = &pOp[-1];

      int tnum = pOp->p2;

      assert( i>iStartAddr );

      assert( pPrior->opcode==OP_Integer );

      if( pPrior->p1==iDb ){

        Index *pIndex;

        if( tnum==pTab->tnum ){

          return 1;

        }

        for(pIndex=pTab->pIndex; pIndex; pIndex=pIndex->pNext){

          if( tnum==pIndex->tnum ){

            return 1;

          }

        }

      }

    }

#ifndef SQLITE_OMIT_VIRTUALTABLE

    if( pOp->opcode==OP_VOpen && pOp->p3==(const char*)pTab->pVtab ){

      assert( pOp->p3!=0 );

      assert( pOp->p3type==P3_VTAB );

      return 1;

    }

#endif

  }

  return 0;

}

#ifndef SQLITE_OMIT_AUTOINCREMENT

/*

** Write out code to initialize the autoincrement logic.  This code

** looks up the current autoincrement value in the sqlite_sequence

** table and stores that value in a memory cell.  Code generated by

** autoIncStep() will keep that memory cell holding the largest

** rowid value.  Code generated by autoIncEnd() will write the new

** largest value of the counter back into the sqlite_sequence table.

**

** This routine returns the index of the mem[] cell that contains

** the maximum rowid counter.

**

** Two memory cells are allocated.  The next memory cell after the

** one returned holds the rowid in sqlite_sequence where we will

** write back the revised maximum rowid.

*/

static int autoIncBegin(

  Parse *pParse,      /* Parsing context */

  int iDb,            /* Index of the database holding pTab */

  Table *pTab         /* The table we are writing to */

){

  int memId = 0;

  if( pTab->autoInc ){

    Vdbe *v = pParse->pVdbe;

    Db *pDb = &pParse->db->aDb[iDb];

    int iCur = pParse->nTab;

    int addr;

    assert( v );

    addr = sqlite3VdbeCurrentAddr(v);

    memId = pParse->nMem+1;

    pParse->nMem += 2;

    sqlite3OpenTable(pParse, iCur, iDb, pDb->pSchema->pSeqTab, OP_OpenRead);

    sqlite3VdbeAddOp(v, OP_Rewind, iCur, addr+13);

    sqlite3VdbeAddOp(v, OP_Column, iCur, 0);

    sqlite3VdbeOp3(v, OP_String8, 0, 0, pTab->zName, 0);

    sqlite3VdbeAddOp(v, OP_Ne, 0x100, addr+12);

    sqlite3VdbeAddOp(v, OP_Rowid, iCur, 0);

    sqlite3VdbeAddOp(v, OP_MemStore, memId-1, 1);

    sqlite3VdbeAddOp(v, OP_Column, iCur, 1);

    sqlite3VdbeAddOp(v, OP_MemStore, memId, 1);

    sqlite3VdbeAddOp(v, OP_Goto, 0, addr+13);

    sqlite3VdbeAddOp(v, OP_Next, iCur, addr+4);

    sqlite3VdbeAddOp(v, OP_Close, iCur, 0);

  }

  return memId;

}

/*

** Update the maximum rowid for an autoincrement calculation.

**

** This routine should be called when the top of the stack holds a

** new rowid that is about to be inserted.  If that new rowid is

** larger than the maximum rowid in the memId memory cell, then the

** memory cell is updated.  The stack is unchanged.

*/

static void autoIncStep(Parse *pParse, int memId){

  if( memId>0 ){

    sqlite3VdbeAddOp(pParse->pVdbe, OP_MemMax, memId, 0);

  }

}

/*

** After doing one or more inserts, the maximum rowid is stored

** in mem[memId].  Generate code to write this value back into the

** the sqlite_sequence table.

*/

static void autoIncEnd(

  Parse *pParse,     /* The parsing context */

  int iDb,           /* Index of the database holding pTab */

  Table *pTab,       /* Table we are inserting into */

  int memId          /* Memory cell holding the maximum rowid */

){

  if( pTab->autoInc ){

    int iCur = pParse->nTab;

    Vdbe *v = pParse->pVdbe;

    Db *pDb = &pParse->db->aDb[iDb];

    int addr;

    assert( v );

    addr = sqlite3VdbeCurrentAddr(v);

    sqlite3OpenTable(pParse, iCur, iDb, pDb->pSchema->pSeqTab, OP_OpenWrite);

    sqlite3VdbeAddOp(v, OP_MemLoad, memId-1, 0);

    sqlite3VdbeAddOp(v, OP_NotNull, -1, addr+7);

    sqlite3VdbeAddOp(v, OP_Pop, 1, 0);

    sqlite3VdbeAddOp(v, OP_NewRowid, iCur, 0);

    sqlite3VdbeOp3(v, OP_String8, 0, 0, pTab->zName, 0);

    sqlite3VdbeAddOp(v, OP_MemLoad, memId, 0);

    sqlite3VdbeAddOp(v, OP_MakeRecord, 2, 0);

    sqlite3VdbeAddOp(v, OP_Insert, iCur, OPFLAG_APPEND);

    sqlite3VdbeAddOp(v, OP_Close, iCur, 0);

  }

}

#else

/*

** If SQLITE_OMIT_AUTOINCREMENT is defined, then the three routines

** above are all no-ops

*/

# define autoIncBegin(A,B,C) (0)

# define autoIncStep(A,B)

# define autoIncEnd(A,B,C,D)

#endif /* SQLITE_OMIT_AUTOINCREMENT */

/* Forward declaration */

static int xferOptimization(

  Parse *pParse,        /* Parser context */

  Table *pDest,         /* The table we are inserting into */

  Select *pSelect,      /* A SELECT statement to use as the data source */

  int onError,          /* How to handle constraint errors */

  int iDbDest           /* The database of pDest */

);

/*

** This routine is call to handle SQL of the following forms:

**

**    insert into TABLE (IDLIST) values(EXPRLIST)

**    insert into TABLE (IDLIST) select

**

** The IDLIST following the table name is always optional.  If omitted,

** then a list of all columns for the table is substituted.  The IDLIST

** appears in the pColumn parameter.  pColumn is NULL if IDLIST is omitted.

**

** The pList parameter holds EXPRLIST in the first form of the INSERT

** statement above, and pSelect is NULL.  For the second form, pList is

** NULL and pSelect is a pointer to the select statement used to generate

** data for the insert.

**

** The code generated follows one of four templates.  For a simple

** select with data coming from a VALUES clause, the code executes

** once straight down through.  The template looks like this:

**

**         open write cursor to <table> and its indices

**         puts VALUES clause expressions onto the stack

**         write the resulting record into <table>

**         cleanup

**

** The three remaining templates assume the statement is of the form

**

**   INSERT INTO <table> SELECT ...

**

** If the SELECT clause is of the restricted form "SELECT * FROM <table2>" -

** in other words if the SELECT pulls all columns from a single table

** and there is no WHERE or LIMIT or GROUP BY or ORDER BY clauses, and

** if <table2> and <table1> are distinct tables but have identical

** schemas, including all the same indices, then a special optimization

** is invoked that copies raw records from <table2> over to <table1>.

** See the xferOptimization() function for the implementation of this

** template.  This is the second template.

**

**         open a write cursor to <table>

**         open read cursor on <table2>

**         transfer all records in <table2> over to <table>

**         close cursors

**         foreach index on <table>

**           open a write cursor on the <table> index

**           open a read cursor on the corresponding <table2> index

**           transfer all records from the read to the write cursors

**           close cursors

**         end foreach

**

** The third template is for when the second template does not apply

** and the SELECT clause does not read from <table> at any time.

** The generated code follows this template:

**

**         goto B

**      A: setup for the SELECT

**         loop over the rows in the SELECT

**           gosub C

**         end loop

**         cleanup after the SELECT

**         goto D

**      B: open write cursor to <table> and its indices

**         goto A

**      C: insert the select result into <table>

**         return

**      D: cleanup

**

** The fourth template is used if the insert statement takes its

** values from a SELECT but the data is being inserted into a table

** that is also read as part of the SELECT.  In the third form,

** we have to use a intermediate table to store the results of

** the select.  The template is like this:

**

**         goto B

**      A: setup for the SELECT

**         loop over the tables in the SELECT

**           gosub C

**         end loop

**         cleanup after the SELECT

**         goto D

**      C: insert the select result into the intermediate table

**         return

**      B: open a cursor to an intermediate table

**         goto A

**      D: open write cursor to <table> and its indices

**         loop over the intermediate table

**           transfer values form intermediate table into <table>

**         end the loop

**         cleanup

*/

void sqlite3Insert(

  Parse *pParse,        /* Parser context */

  SrcList *pTabList,    /* Name of table into which we are inserting */

  ExprList *pList,      /* List of values to be inserted */

  Select *pSelect,      /* A SELECT statement to use as the data source */

  IdList *pColumn,      /* Column names corresponding to IDLIST. */

  int onError           /* How to handle constraint errors */

){

  Table *pTab;          /* The table to insert into */

  char *zTab;           /* Name of the table into which we are inserting */

  const char *zDb;      /* Name of the database holding this table */

  int i, j, idx;        /* Loop counters */

  Vdbe *v;              /* Generate code into this virtual machine */

  Index *pIdx;          /* For looping over indices of the table */

  int nColumn;          /* Number of columns in the data */

  int base = 0;         /* VDBE Cursor number for pTab */

  int iCont=0,iBreak=0; /* Beginning and end of the loop over srcTab */

  sqlite3 *db;          /* The main database structure */

  int keyColumn = -1;   /* Column that is the INTEGER PRIMARY KEY */

  int endOfLoop;        /* Label for the end of the insertion loop */

  int useTempTable = 0; /* Store SELECT results in intermediate table */

  int srcTab = 0;       /* Data comes from this temporary cursor if >=0 */

  int iSelectLoop = 0;  /* Address of code that implements the SELECT */

  int iCleanup = 0;     /* Address of the cleanup code */

  int iInsertBlock = 0; /* Address of the subroutine used to insert data */

  int iCntMem = 0;      /* Memory cell used for the row counter */

  int newIdx = -1;      /* Cursor for the NEW table */

  Db *pDb;              /* The database containing table being inserted into */

  int counterMem = 0;   /* Memory cell holding AUTOINCREMENT counter */

  int appendFlag = 0;   /* True if the insert is likely to be an append */

  int iDb;

  int nHidden = 0;

#ifndef SQLITE_OMIT_TRIGGER

  int isView;                 /* True if attempting to insert into a view */

  int triggers_exist = 0;     /* True if there are FOR EACH ROW triggers */

#endif

  db = pParse->db;

  if( pParse->nErr || db->mallocFailed ){

    goto insert_cleanup;

  }

  /* Locate the table into which we will be inserting new information.

  */

  assert( pTabList->nSrc==1 );

  zTab = pTabList->a[0].zName;

  if( zTab==0 ) goto insert_cleanup;

  pTab = sqlite3SrcListLookup(pParse, pTabList);

  if( pTab==0 ){

    goto insert_cleanup;

  }

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

  assert( iDb<db->nDb );

  pDb = &db->aDb[iDb];

  zDb = pDb->zName;

  if( sqlite3AuthCheck(pParse, SQLITE_INSERT, pTab->zName, 0, zDb) ){

    goto insert_cleanup;

  }

  /* Figure out if we have any triggers and if the table being

  ** inserted into is a view

  */

#ifndef SQLITE_OMIT_TRIGGER

  triggers_exist = sqlite3TriggersExist(pParse, pTab, TK_INSERT, 0);

  isView = pTab->pSelect!=0;

#else

# define triggers_exist 0

# define isView 0

#endif

#ifdef SQLITE_OMIT_VIEW

# undef isView

# define isView 0

#endif

  /* Ensure that:

  *  (a) the table is not read-only, 

  *  (b) that if it is a view then ON INSERT triggers exist

  */

  if( sqlite3IsReadOnly(pParse, pTab, triggers_exist) ){

    goto insert_cleanup;

  }

  assert( pTab!=0 );

  /* If pTab is really a view, make sure it has been initialized.

  ** ViewGetColumnNames() is a no-op if pTab is not a view (or virtual 

  ** module table).

  */

  if( sqlite3ViewGetColumnNames(pParse, pTab) ){

    goto insert_cleanup;

  }

  /* Allocate a VDBE

  */

  v = sqlite3GetVdbe(pParse);

  if( v==0 ) goto insert_cleanup;

  if( pParse->nested==0 ) sqlite3VdbeCountChanges(v);

  sqlite3BeginWriteOperation(pParse, pSelect || triggers_exist, iDb);

  /* if there are row triggers, allocate a temp table for new.* references. */

  if( triggers_exist ){

    newIdx = pParse->nTab++;

  }

#ifndef SQLITE_OMIT_XFER_OPT

  /* If the statement is of the form

  **

  **       INSERT INTO <table1> SELECT * FROM <table2>;

  **

  ** Then special optimizations can be applied that make the transfer

  ** very fast and which reduce fragmentation of indices.

  */

  if( pColumn==0 && xferOptimization(pParse, pTab, pSelect, onError, iDb) ){

    assert( !triggers_exist );

    assert( pList==0 );

    goto insert_cleanup;

  }

#endif /* SQLITE_OMIT_XFER_OPT */

  /* If this is an AUTOINCREMENT table, look up the sequence number in the

  ** sqlite_sequence table and store it in memory cell counterMem.  Also

  ** remember the rowid of the sqlite_sequence table entry in memory cell

  ** counterRowid.

  */

  counterMem = autoIncBegin(pParse, iDb, pTab);

  /* Figure out how many columns of data are supplied.  If the data

  ** is coming from a SELECT statement, then this step also generates

  ** all the code to implement the SELECT statement and invoke a subroutine

  ** to process each row of the result. (Template 2.) If the SELECT

  ** statement uses the the table that is being inserted into, then the

  ** subroutine is also coded here.  That subroutine stores the SELECT

  ** results in a temporary table. (Template 3.)

  */

  if( pSelect ){

    /* Data is coming from a SELECT.  Generate code to implement that SELECT

    */

    int rc, iInitCode;

    iInitCode = sqlite3VdbeAddOp(v, OP_Goto, 0, 0);

    iSelectLoop = sqlite3VdbeCurrentAddr(v);

    iInsertBlock = sqlite3VdbeMakeLabel(v);

    /* Resolve the expressions in the SELECT statement and execute it. */

    rc = sqlite3Select(pParse, pSelect, SRT_Subroutine, iInsertBlock,0,0,0,0);

    if( rc || pParse->nErr || db->mallocFailed ){

      goto insert_cleanup;

    }

    iCleanup = sqlite3VdbeMakeLabel(v);

    sqlite3VdbeAddOp(v, OP_Goto, 0, iCleanup);

    assert( pSelect->pEList );

    nColumn = pSelect->pEList->nExpr;

    /* Set useTempTable to TRUE if the result of the SELECT statement

    ** should be written into a temporary table.  Set to FALSE if each

    ** row of the SELECT can be written directly into the result table.

    **

    ** A temp table must be used if the table being updated is also one

    ** of the tables being read by the SELECT statement.  Also use a 

    ** temp table in the case of row triggers.

    */

    if( triggers_exist || readsTable(v, iSelectLoop, iDb, pTab) ){

      useTempTable = 1;

    }

    if( useTempTable ){

      /* Generate the subroutine that SELECT calls to process each row of

      ** the result.  Store the result in a temporary table

      */

      srcTab = pParse->nTab++;

      sqlite3VdbeResolveLabel(v, iInsertBlock);

      sqlite3VdbeAddOp(v, OP_StackDepth, -1, 0);

      sqlite3VdbeAddOp(v, OP_MakeRecord, nColumn, 0);

      sqlite3VdbeAddOp(v, OP_NewRowid, srcTab, 0);

      sqlite3VdbeAddOp(v, OP_Pull, 1, 0);

      sqlite3VdbeAddOp(v, OP_Insert, srcTab, OPFLAG_APPEND);

      sqlite3VdbeAddOp(v, OP_Return, 0, 0);

      /* The following code runs first because the GOTO at the very top

      ** of the program jumps to it.  Create the temporary table, then jump

      ** back up and execute the SELECT code above.

      */

      sqlite3VdbeJumpHere(v, iInitCode);

      sqlite3VdbeAddOp(v, OP_OpenEphemeral, srcTab, 0);

      sqlite3VdbeAddOp(v, OP_SetNumColumns, srcTab, nColumn);

      sqlite3VdbeAddOp(v, OP_Goto, 0, iSelectLoop);

      sqlite3VdbeResolveLabel(v, iCleanup);

    }else{