/*

** 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.c,v 1.249 2008/08/20 16:35:10 drh Exp $

*/

#include "sqliteInt.h"

/*

** Set P4 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

**

** An extra 'b' is appended to the end of the string to cover the

** rowid that appears as the last column in every index.

*/

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 *)sqlite3Malloc(pIdx->nColumn+2);

    if( !pIdx->zColAff ){

      db->mallocFailed = 1;

      return;

    }

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

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

    }

    pIdx->zColAff[n++] = SQLITE_AFF_NONE;

    pIdx->zColAff[n] = 0;

  }

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

}

/*

** Set P4 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 *)sqlite3Malloc(pTab->nCol+1);

    if( !zColAff ){

      db->mallocFailed = 1;

      return;

    }

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

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

    }

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

    pTab->zColAff = zColAff;

  }

  sqlite3VdbeChangeP4(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 && pOp->p3==iDb ){

      Index *pIndex;

      int tnum = pOp->p2;

      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->p4.pVtab==pTab->pVtab ){

      assert( pOp->p4.pVtab!=0 );

      assert( pOp->p4type==P4_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 register.  Code generated by

** autoIncStep() will keep that register 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.

**

** Three consecutive registers are allocated by this routine.  The

** first two hold the name of the target table and the maximum rowid 

** inserted into the target table, respectively.

** The third holds the rowid in sqlite_sequence where we will

** write back the revised maximum rowid.  This routine returns the

** index of the second of these three registers.

*/

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;      /* Register holding maximum rowid */

  if( pTab->tabFlags & TF_Autoincrement ){

    Vdbe *v = pParse->pVdbe;

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

    int iCur = pParse->nTab;

    int addr;               /* Address of the top of the loop */

    assert( v );

    pParse->nMem++;         /* Holds name of table */

    memId = ++pParse->nMem;

    pParse->nMem++;

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

    addr = sqlite3VdbeCurrentAddr(v);

    sqlite3VdbeAddOp4(v, OP_String8, 0, memId-1, 0, pTab->zName, 0);

    sqlite3VdbeAddOp2(v, OP_Rewind, iCur, addr+9);

    sqlite3VdbeAddOp3(v, OP_Column, iCur, 0, memId);

    sqlite3VdbeAddOp3(v, OP_Ne, memId-1, addr+7, memId);

    sqlite3VdbeChangeP5(v, SQLITE_JUMPIFNULL);

    sqlite3VdbeAddOp2(v, OP_Rowid, iCur, memId+1);

    sqlite3VdbeAddOp3(v, OP_Column, iCur, 1, memId);

    sqlite3VdbeAddOp2(v, OP_Goto, 0, addr+9);

    sqlite3VdbeAddOp2(v, OP_Next, iCur, addr+2);

    sqlite3VdbeAddOp2(v, OP_Integer, 0, memId);

    sqlite3VdbeAddOp2(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, int regRowid){

  if( memId>0 ){

    sqlite3VdbeAddOp2(pParse->pVdbe, OP_MemMax, memId, regRowid);

  }

}

/*

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

** in reg[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->tabFlags & TF_Autoincrement ){

    int iCur = pParse->nTab;

    Vdbe *v = pParse->pVdbe;

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

    int j1;

    int iRec = ++pParse->nMem;    /* Memory cell used for record */

    assert( v );

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

    j1 = sqlite3VdbeAddOp1(v, OP_NotNull, memId+1);

    sqlite3VdbeAddOp2(v, OP_NewRowid, iCur, memId+1);

    sqlite3VdbeJumpHere(v, j1);

    sqlite3VdbeAddOp3(v, OP_MakeRecord, memId-1, 2, iRec);

    sqlite3VdbeAddOp3(v, OP_Insert, iCur, iRec, memId+1);

    sqlite3VdbeChangeP5(v, OPFLAG_APPEND);

    sqlite3VdbeAddOp1(v, OP_Close, iCur);

  }

}

#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,C)

# 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.  Pseudo-code follows (we call this

** the "1st template"):

**

**         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 2nd 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 3rd 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:

**

**         EOF <- 0

**         X <- A

**         goto B

**      A: setup for the SELECT

**         loop over the rows in the SELECT

**           load values into registers R..R+n

**           yield X

**         end loop

**         cleanup after the SELECT

**         EOF <- 1

**         yield X

**         goto A

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

**      C: yield X

**         if EOF goto D

**         insert the select result into <table> from R..R+n

**         goto C

**      D: cleanup

**

** The 4th 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:

**

**         EOF <- 0

**         X <- A

**         goto B

**      A: setup for the SELECT

**         loop over the tables in the SELECT

**           load value into register R..R+n

**           yield X

**         end loop

**         cleanup after the SELECT

**         EOF <- 1

**         yield X

**         halt-error

**      B: open temp table

**      L: yield X

**         if EOF goto M

**         insert row from R..R+n into temp table

**         goto L

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

**         rewind temp table

**      C: loop over rows of intermediate table

**           transfer values form intermediate table into <table>

**         end loop

**      D: 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 */

){

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

  Table *pTab;          /* The table to insert into.  aka TABLE */

  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 nHidden = 0;      /* Number of hidden columns if TABLE is virtual */

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

  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 addrInsTop = 0;   /* Jump to label "D" */

  int addrCont = 0;     /* Top of insert loop. Label "C" in templates 3 and 4 */

  int addrSelect = 0;   /* Address of coroutine that implements the SELECT */

  SelectDest dest;      /* Destination for SELECT on rhs of INSERT */

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

  int iDb;              /* Index of database holding TABLE */

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

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

  /* Register allocations */

  int regFromSelect;    /* Base register for data coming from SELECT */

  int regAutoinc = 0;   /* Register holding the AUTOINCREMENT counter */

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

  int regIns;           /* Block of regs holding rowid+data being inserted */

  int regRowid;         /* registers holding insert rowid */

  int regData;          /* register holding first column to insert */

  int regRecord;        /* Holds the assemblied row record */

  int regEof;           /* Register recording end of SELECT data */

  int *aRegIdx = 0;     /* One register allocated to each index */

#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.

  **

  ** This is the 2nd template.

  */

  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 regAutoinc.

  */

  regAutoinc = autoIncBegin(pParse, iDb, pTab);

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

  ** is coming from a SELECT statement, then generate a co-routine that

  ** produces a single row of the SELECT on each invocation.  The

  ** co-routine is the common header to the 3rd and 4th templates.

  */

  if( pSelect ){

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

    ** as a co-routine.  The code is common to both the 3rd and 4th

    ** templates:

    **

    **         EOF <- 0

    **         X <- A

    **         goto B

    **      A: setup for the SELECT

    **         loop over the tables in the SELECT

    **           load value into register R..R+n

    **           yield X

    **         end loop

    **         cleanup after the SELECT

    **         EOF <- 1

    **         yield X

    **         halt-error

    **

    ** On each invocation of the co-routine, it puts a single row of the

    ** SELECT result into registers dest.iMem...dest.iMem+dest.nMem-1.

    ** (These output registers are allocated by sqlite3Select().)  When

    ** the SELECT completes, it sets the EOF flag stored in regEof.

    */

    int rc, j1;

    regEof = ++pParse->nMem;

    sqlite3VdbeAddOp2(v, OP_Integer, 0, regEof);      /* EOF <- 0 */

    VdbeComment((v, "SELECT eof flag"));

    sqlite3SelectDestInit(&dest, SRT_Coroutine, ++pParse->nMem);