/*

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

** in order to generate code for DELETE FROM statements.

**

** $Id: delete.c,v 1.182 2008/10/10 23:48:26 drh Exp $

*/

#include "sqliteInt.h"

/*

** Look up every table that is named in pSrc.  If any table is not found,

** add an error message to pParse->zErrMsg and return NULL.  If all tables

** are found, return a pointer to the last table.

*/

Table *sqlite3SrcListLookup(Parse *pParse, SrcList *pSrc){

  struct SrcList_item *pItem = pSrc->a;

  Table *pTab;

  assert( pItem && pSrc->nSrc==1 );

  pTab = sqlite3LocateTable(pParse, 0, pItem->zName, pItem->zDatabase);

  sqlite3DeleteTable(pItem->pTab);

  pItem->pTab = pTab;

  if( pTab ){

    pTab->nRef++;

  }

  if( sqlite3IndexedByLookup(pParse, pItem) ){

    pTab = 0;

  }

  return pTab;

}

/*

** Check to make sure the given table is writable.  If it is not

** writable, generate an error message and return 1.  If it is

** writable return 0;

*/

int sqlite3IsReadOnly(Parse *pParse, Table *pTab, int viewOk){

  if( ((pTab->tabFlags & TF_Readonly)!=0

        && (pParse->db->flags & SQLITE_WriteSchema)==0

        && pParse->nested==0) 

#ifndef SQLITE_OMIT_VIRTUALTABLE

      || (pTab->pMod && pTab->pMod->pModule->xUpdate==0)

#endif

  ){

    sqlite3ErrorMsg(pParse, "table %s may not be modified", pTab->zName);

    return 1;

  }

#ifndef SQLITE_OMIT_VIEW

  if( !viewOk && pTab->pSelect ){

    sqlite3ErrorMsg(pParse,"cannot modify %s because it is a view",pTab->zName);

    return 1;

  }

#endif

  return 0;

}

/*

** Generate code that will open a table for reading.

*/

void sqlite3OpenTable(

  Parse *p,       /* Generate code into this VDBE */

  int iCur,       /* The cursor number of the table */

  int iDb,        /* The database index in sqlite3.aDb[] */

  Table *pTab,    /* The table to be opened */

  int opcode      /* OP_OpenRead or OP_OpenWrite */

){

  Vdbe *v;

  if( IsVirtual(pTab) ) return;

  v = sqlite3GetVdbe(p);

  assert( opcode==OP_OpenWrite || opcode==OP_OpenRead );

  sqlite3TableLock(p, iDb, pTab->tnum, (opcode==OP_OpenWrite), pTab->zName);

  sqlite3VdbeAddOp2(v, OP_SetNumColumns, 0, pTab->nCol);

  sqlite3VdbeAddOp3(v, opcode, iCur, pTab->tnum, iDb);

  VdbeComment((v, "%s", pTab->zName));

}

#if !defined(SQLITE_OMIT_VIEW) && !defined(SQLITE_OMIT_TRIGGER)

/*

** Evaluate a view and store its result in an ephemeral table.  The

** pWhere argument is an optional WHERE clause that restricts the

** set of rows in the view that are to be added to the ephemeral table.

*/

void sqlite3MaterializeView(

  Parse *pParse,       /* Parsing context */

  Table *pView,        /* View definition */

  Expr *pWhere,        /* Optional WHERE clause to be added */

  int iCur             /* Cursor number for ephemerial table */

){

  SelectDest dest;

  Select *pDup;

  sqlite3 *db = pParse->db;

  pDup = sqlite3SelectDup(db, pView->pSelect);

  if( pWhere ){

    SrcList *pFrom;

    Token viewName;

    pWhere = sqlite3ExprDup(db, pWhere);

    viewName.z = (u8*)pView->zName;

    viewName.n = (unsigned int)strlen((const char*)viewName.z);

    pFrom = sqlite3SrcListAppendFromTerm(pParse, 0, 0, 0, &viewName, pDup, 0,0);

    pDup = sqlite3SelectNew(pParse, 0, pFrom, pWhere, 0, 0, 0, 0, 0, 0);

  }

  sqlite3SelectDestInit(&dest, SRT_EphemTab, iCur);

  sqlite3Select(pParse, pDup, &dest);

  sqlite3SelectDelete(db, pDup);

}

#endif /* !defined(SQLITE_OMIT_VIEW) && !defined(SQLITE_OMIT_TRIGGER) */

#if defined(SQLITE_ENABLE_UPDATE_DELETE_LIMIT) && !defined(SQLITE_OMIT_SUBQUERY)

/*

** Generate an expression tree to implement the WHERE, ORDER BY,

** and LIMIT/OFFSET portion of DELETE and UPDATE statements.

**

**     DELETE FROM table_wxyz WHERE a<5 ORDER BY a LIMIT 1;

**                            \__________________________/

**                               pLimitWhere (pInClause)

*/

Expr *sqlite3LimitWhere(

  Parse *pParse,               /* The parser context */

  SrcList *pSrc,               /* the FROM clause -- which tables to scan */

  Expr *pWhere,                /* The WHERE clause.  May be null */

  ExprList *pOrderBy,          /* The ORDER BY clause.  May be null */

  Expr *pLimit,                /* The LIMIT clause.  May be null */

  Expr *pOffset,               /* The OFFSET clause.  May be null */

  char *zStmtType              /* Either DELETE or UPDATE.  For error messages. */

){

  Expr *pWhereRowid = NULL;    /* WHERE rowid .. */

  Expr *pInClause = NULL;      /* WHERE rowid IN ( select ) */

  Expr *pSelectRowid = NULL;   /* SELECT rowid ... */

  ExprList *pEList = NULL;     /* Expression list contaning only pSelectRowid */

  SrcList *pSelectSrc = NULL;  /* SELECT rowid FROM x ... (dup of pSrc) */

  Select *pSelect = NULL;      /* Complete SELECT tree */

  /* Check that there isn't an ORDER BY without a LIMIT clause.

  */

  if( pOrderBy && (pLimit == 0) ) {

    sqlite3ErrorMsg(pParse, "ORDER BY without LIMIT on %s", zStmtType);

    pParse->parseError = 1;

    goto limit_where_cleanup_2;

  }

  /* We only need to generate a select expression if there

  ** is a limit/offset term to enforce.

  */

  if( pLimit == 0 ) {

    /* if pLimit is null, pOffset will always be null as well. */

    assert( pOffset == 0 );

    return pWhere;

  }

  /* Generate a select expression tree to enforce the limit/offset 

  ** term for the DELETE or UPDATE statement.  For example:

  **   DELETE FROM table_a WHERE col1=1 ORDER BY col2 LIMIT 1 OFFSET 1

  ** becomes:

  **   DELETE FROM table_a WHERE rowid IN ( 

  **     SELECT rowid FROM table_a WHERE col1=1 ORDER BY col2 LIMIT 1 OFFSET 1

  **   );

  */

  pSelectRowid = sqlite3Expr(pParse->db, TK_ROW, 0, 0, 0);

  if( pSelectRowid == 0 ) goto limit_where_cleanup_2;

  pEList = sqlite3ExprListAppend(pParse, 0, pSelectRowid, 0);

  if( pEList == 0 ) goto limit_where_cleanup_2;

  /* duplicate the FROM clause as it is needed by both the DELETE/UPDATE tree

  ** and the SELECT subtree. */

  pSelectSrc = sqlite3SrcListDup(pParse->db, pSrc);

  if( pSelectSrc == 0 ) {

    sqlite3ExprListDelete(pParse->db, pEList);

    goto limit_where_cleanup_2;

  }

  /* generate the SELECT expression tree. */

  pSelect = sqlite3SelectNew(pParse,pEList,pSelectSrc,pWhere,0,0,pOrderBy,0,pLimit,pOffset);

  if( pSelect == 0 ) return 0;

  /* now generate the new WHERE rowid IN clause for the DELETE/UDPATE */

  pWhereRowid = sqlite3Expr(pParse->db, TK_ROW, 0, 0, 0);

  if( pWhereRowid == 0 ) goto limit_where_cleanup_1;

  pInClause = sqlite3PExpr(pParse, TK_IN, pWhereRowid, 0, 0);

  if( pInClause == 0 ) goto limit_where_cleanup_1;

  pInClause->pSelect = pSelect;

  sqlite3ExprSetHeight(pParse, pInClause);

  return pInClause;

  /* something went wrong. clean up anything allocated. */

limit_where_cleanup_1:

  sqlite3SelectDelete(pParse->db, pSelect);

  return 0;

limit_where_cleanup_2:

  sqlite3ExprDelete(pParse->db, pWhere);

  sqlite3ExprListDelete(pParse->db, pOrderBy);

  sqlite3ExprDelete(pParse->db, pLimit);

  sqlite3ExprDelete(pParse->db, pOffset);

  return 0;

}

#endif /* defined(SQLITE_ENABLE_UPDATE_DELETE_LIMIT) && !defined(SQLITE_OMIT_SUBQUERY) */

/*

** Generate code for a DELETE FROM statement.

**

**     DELETE FROM table_wxyz WHERE a<5 AND b NOT NULL;

**                 \________/       \________________/

**                  pTabList              pWhere

*/

void sqlite3DeleteFrom(

  Parse *pParse,         /* The parser context */

  SrcList *pTabList,     /* The table from which we should delete things */

  Expr *pWhere           /* The WHERE clause.  May be null */

){

  Vdbe *v;               /* The virtual database engine */

  Table *pTab;           /* The table from which records will be deleted */

  const char *zDb;       /* Name of database holding pTab */

  int end, addr = 0;     /* A couple addresses of generated code */

  int i;                 /* Loop counter */

  WhereInfo *pWInfo;     /* Information about the WHERE clause */

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

  int iCur;              /* VDBE Cursor number for pTab */

  sqlite3 *db;           /* Main database structure */

  AuthContext sContext;  /* Authorization context */

  int oldIdx = -1;       /* Cursor for the OLD table of AFTER triggers */

  NameContext sNC;       /* Name context to resolve expressions in */

  int iDb;               /* Database number */

  int memCnt = 0;        /* Memory cell used for change counting */

#ifndef SQLITE_OMIT_TRIGGER

  int isView;                  /* True if attempting to delete from a view */

  int triggers_exist = 0;      /* True if any triggers exist */

#endif

  int iBeginAfterTrigger;      /* Address of after trigger program */

  int iEndAfterTrigger;        /* Exit of after trigger program */

  int iBeginBeforeTrigger;     /* Address of before trigger program */

  int iEndBeforeTrigger;       /* Exit of before trigger program */

  u32 old_col_mask = 0;        /* Mask of OLD.* columns in use */

  sContext.pParse = 0;

  db = pParse->db;

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

    goto delete_from_cleanup;

  }

  assert( pTabList->nSrc==1 );

  /* Locate the table which we want to delete.  This table has to be

  ** put in an SrcList structure because some of the subroutines we

  ** will be calling are designed to work with multiple tables and expect

  ** an SrcList* parameter instead of just a Table* parameter.

  */

  pTab = sqlite3SrcListLookup(pParse, pTabList);

  if( pTab==0 )  goto delete_from_cleanup;

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

  ** deleted from is a view

  */

#ifndef SQLITE_OMIT_TRIGGER

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

  isView = pTab->pSelect!=0;

#else

# define triggers_exist 0

# define isView 0

#endif

#ifdef SQLITE_OMIT_VIEW

# undef isView

# define isView 0

#endif

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

    goto delete_from_cleanup;

  }

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

  assert( iDb<db->nDb );

  zDb = db->aDb[iDb].zName;

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

    goto delete_from_cleanup;

  }

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

  */

  if( sqlite3ViewGetColumnNames(pParse, pTab) ){

    goto delete_from_cleanup;

  }

  /* Allocate a cursor used to store the old.* data for a trigger.

  */

  if( triggers_exist ){ 

    oldIdx = pParse->nTab++;

  }

  /* Assign  cursor number to the table and all its indices.

  */

  assert( pTabList->nSrc==1 );

  iCur = pTabList->a[0].iCursor = pParse->nTab++;

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

    pParse->nTab++;

  }

  /* Start the view context

  */

  if( isView ){

    sqlite3AuthContextPush(pParse, &sContext, pTab->zName);

  }

  /* Begin generating code.

  */

  v = sqlite3GetVdbe(pParse);

  if( v==0 ){

    goto delete_from_cleanup;

  }

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

  sqlite3BeginWriteOperation(pParse, triggers_exist, iDb);

  if( triggers_exist ){

    int orconf = ((pParse->trigStack)?pParse->trigStack->orconf:OE_Default);

    int iGoto = sqlite3VdbeAddOp0(v, OP_Goto);

    addr = sqlite3VdbeMakeLabel(v);

    iBeginBeforeTrigger = sqlite3VdbeCurrentAddr(v);

    (void)sqlite3CodeRowTrigger(pParse, TK_DELETE, 0, TRIGGER_BEFORE, pTab,

        -1, oldIdx, orconf, addr, &old_col_mask, 0);

    iEndBeforeTrigger = sqlite3VdbeAddOp0(v, OP_Goto);

    iBeginAfterTrigger = sqlite3VdbeCurrentAddr(v);

    (void)sqlite3CodeRowTrigger(pParse, TK_DELETE, 0, TRIGGER_AFTER, pTab, -1,

        oldIdx, orconf, addr, &old_col_mask, 0);

    iEndAfterTrigger = sqlite3VdbeAddOp0(v, OP_Goto);

    sqlite3VdbeJumpHere(v, iGoto);

  }

  /* If we are trying to delete from a view, realize that view into

  ** a ephemeral table.

  */

#if !defined(SQLITE_OMIT_VIEW) && !defined(SQLITE_OMIT_TRIGGER)

  if( isView ){

    sqlite3MaterializeView(pParse, pTab, pWhere, iCur);

  }

#endif

  /* Resolve the column names in the WHERE clause.

  */

  memset(&sNC, 0, sizeof(sNC));

  sNC.pParse = pParse;

  sNC.pSrcList = pTabList;

  if( sqlite3ResolveExprNames(&sNC, pWhere) ){

    goto delete_from_cleanup;

  }

  /* Initialize the counter of the number of rows deleted, if

  ** we are counting rows.

  */

  if( db->flags & SQLITE_CountRows ){

    memCnt = ++pParse->nMem;

    sqlite3VdbeAddOp2(v, OP_Integer, 0, memCnt);

  }

#ifndef SQLITE_OMIT_TRUNCATE_OPTIMIZATION

  /* Special case: A DELETE without a WHERE clause deletes everything.

  ** It is easier just to erase the whole table.  Note, however, that

  ** this means that the row change count will be incorrect.

  */

  if( pWhere==0 && !triggers_exist && !IsVirtual(pTab) ){

    if( db->flags & SQLITE_CountRows ){

      /* If counting rows deleted, just count the total number of

      ** entries in the table. */

      int addr2;

      if( !isView ){

        sqlite3OpenTable(pParse, iCur, iDb, pTab, OP_OpenRead);

      }

      sqlite3VdbeAddOp2(v, OP_Rewind, iCur, sqlite3VdbeCurrentAddr(v)+2);

      addr2 = sqlite3VdbeAddOp2(v, OP_AddImm, memCnt, 1);

      sqlite3VdbeAddOp2(v, OP_Next, iCur, addr2);

      sqlite3VdbeAddOp1(v, OP_Close, iCur);

    }

    if( !isView ){

      sqlite3VdbeAddOp2(v, OP_Clear, pTab->tnum, iDb);

      if( !pParse->nested ){

        sqlite3VdbeChangeP4(v, -1, pTab->zName, P4_STATIC);

      }

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

        assert( pIdx->pSchema==pTab->pSchema );

        sqlite3VdbeAddOp2(v, OP_Clear, pIdx->tnum, iDb);

      }

    }

  }else

#endif /* SQLITE_OMIT_TRUNCATE_OPTIMIZATION */

  /* The usual case: There is a WHERE clause so we have to scan through

  ** the table and pick which records to delete.

  */

  {

    int iRowid = ++pParse->nMem;    /* Used for storing rowid values. */

    /* Begin the database scan

    */

    pWInfo = sqlite3WhereBegin(pParse, pTabList, pWhere, 0, 0);

    if( pWInfo==0 ) goto delete_from_cleanup;

    /* Remember the rowid of every item to be deleted.

    */

    sqlite3VdbeAddOp2(v, IsVirtual(pTab) ? OP_VRowid : OP_Rowid, iCur, iRowid);

    sqlite3VdbeAddOp1(v, OP_FifoWrite, iRowid);

    if( db->flags & SQLITE_CountRows ){

      sqlite3VdbeAddOp2(v, OP_AddImm, memCnt, 1);

    }

    /* End the database scan loop.

    */

    sqlite3WhereEnd(pWInfo);

    /* Open the pseudo-table used to store OLD if there are triggers.

    */

    if( triggers_exist ){

      sqlite3VdbeAddOp2(v, OP_SetNumColumns, 0, pTab->nCol);

      sqlite3VdbeAddOp1(v, OP_OpenPseudo, oldIdx);

    }

    /* Delete every item whose key was written to the list during the

    ** database scan.  We have to delete items after the scan is complete

    ** because deleting an item can change the scan order.

    */

    end = sqlite3VdbeMakeLabel(v);

    if( !isView ){

      /* Open cursors for the table we are deleting from and 

      ** all its indices.

      */

      sqlite3OpenTableAndIndices(pParse, pTab, iCur, OP_OpenWrite);

    }

    /* This is the beginning of the delete loop. If a trigger encounters

    ** an IGNORE constraint, it jumps back to here.

    */

    if( triggers_exist ){

      sqlite3VdbeResolveLabel(v, addr);

    }

    addr = sqlite3VdbeAddOp2(v, OP_FifoRead, iRowid, end);

    if( triggers_exist ){

      int iData = ++pParse->nMem;   /* For storing row data of OLD table */

      /* If the record is no longer present in the table, jump to the

      ** next iteration of the loop through the contents of the fifo.

      */

      sqlite3VdbeAddOp3(v, OP_NotExists, iCur, addr, iRowid);

      /* Populate the OLD.* pseudo-table */

      if( old_col_mask ){

        sqlite3VdbeAddOp2(v, OP_RowData, iCur, iData);

      }else{

        sqlite3VdbeAddOp2(v, OP_Null, 0, iData);

      }

      sqlite3VdbeAddOp3(v, OP_Insert, oldIdx, iData, iRowid);

      /* Jump back and run the BEFORE triggers */

      sqlite3VdbeAddOp2(v, OP_Goto, 0, iBeginBeforeTrigger);

      sqlite3VdbeJumpHere(v, iEndBeforeTrigger);

    }

    if( !isView ){

      /* Delete the row */

#ifndef SQLITE_OMIT_VIRTUALTABLE

      if( IsVirtual(pTab) ){

        const char *pVtab = (const char *)pTab->pVtab;

        sqlite3VtabMakeWritable(pParse, pTab);

        sqlite3VdbeAddOp4(v, OP_VUpdate, 0, 1, iRowid, pVtab, P4_VTAB);

      }else

#endif

      {

        sqlite3GenerateRowDelete(pParse, pTab, iCur, iRowid, pParse->nested==0);

      }

    }

    /* If there are row triggers, close all cursors then invoke

    ** the AFTER triggers

    */

    if( triggers_exist ){

      /* Jump back and run the AFTER triggers */

      sqlite3VdbeAddOp2(v, OP_Goto, 0, iBeginAfterTrigger);

      sqlite3VdbeJumpHere(v, iEndAfterTrigger);

    }

    /* End of the delete loop */

    sqlite3VdbeAddOp2(v, OP_Goto, 0, addr);

    sqlite3VdbeResolveLabel(v, end);

    /* Close the cursors after the loop if there are no row triggers */

    if( !isView  && !IsVirtual(pTab) ){

      for(i=1, pIdx=pTab->pIndex; pIdx; i++, pIdx=pIdx->pNext){

        sqlite3VdbeAddOp2(v, OP_Close, iCur + i, pIdx->tnum);

      }

      sqlite3VdbeAddOp1(v, OP_Close, iCur);

    }

  }

  /*

  ** Return the number of rows that were deleted. If this routine is 

  ** generating code because of a call to sqlite3NestedParse(), do not

  ** invoke the callback function.

  */

  if( db->flags & SQLITE_CountRows && pParse->nested==0 && !pParse->trigStack ){

    sqlite3VdbeAddOp2(v, OP_ResultRow, memCnt, 1);

    sqlite3VdbeSetNumCols(v, 1);

    sqlite3VdbeSetColName(v, 0, COLNAME_NAME, "rows deleted", P4_STATIC);

  }

delete_from_cleanup:

  sqlite3AuthContextPop(&sContext);

  sqlite3SrcListDelete(db, pTabList);

  sqlite3ExprDelete(db, pWhere);

  return;

}

/*

** This routine generates VDBE code that causes a single row of a

** single table to be deleted.

**

** The VDBE must be in a particular state when this routine is called.

** These are the requirements: