/*** 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.***************************************************************************** The code in this file implements execution method of the ** Virtual Database Engine (VDBE).  A separate file ("vdbeaux.c")** handles housekeeping details such as creating and deleting** VDBE instances.  This file is solely interested in executing** the VDBE program.**** In the external interface, an "sqlite_vm*" is an opaque pointer** to a VDBE.**** The SQL parser generates a program which is then executed by** the VDBE to do the work of the SQL statement.  VDBE programs are ** similar in form to assembly language.  The program consists of** a linear sequence of operations.  Each operation has an opcode ** and 3 operands.  Operands P1 and P2 are integers.  Operand P3 ** is a null-terminated string.   The P2 operand must be non-negative.** Opcodes will typically ignore one or more operands.  Many opcodes** ignore all three operands.**** Computation results are stored on a stack.  Each entry on the** stack is either an integer, a null-terminated string, a floating point** number, or the SQL "NULL" value.  An inplicit conversion from one** type to the other occurs as necessary.** ** Most of the code in this file is taken up by the sqliteVdbeExec()** function which does the work of interpreting a VDBE program.** But other routines are also provided to help in building up** a program instruction by instruction.**** Various scripts scan this source file in order to generate HTML** documentation, headers files, or other derived files.  The formatting** of the code in this file is, therefore, important.  See other comments** in this file for details.  If in doubt, do not deviate from existing** commenting and indentation practices when changing or adding code.**** $Id: vdbe.c,v 1.268.2.4 2004/10/01 15:11:13 drh Exp $*/#include "sqliteInt.h"#include "os.h"#include <ctype.h>#include "vdbeInt.h"/*** The following global variable is incremented every time a cursor** moves, either by the OP_MoveTo or the OP_Next opcode.  The test** procedures use this information to make sure that indices are** working correctly.  This variable has no function other than to** help verify the correct operation of the library.*/int sqlite_search_count = 0;/*** When this global variable is positive, it gets decremented once before** each instruction in the VDBE.  When reaches zero, the SQLITE_Interrupt** of the db.flags field is set in order to simulate an interrupt.**** This facility is used for testing purposes only.  It does not function** in an ordinary build.*/int sqlite_interrupt_count = 0;/*** Advance the virtual machine to the next output row.**** The return vale will be either SQLITE_BUSY, SQLITE_DONE, ** SQLITE_ROW, SQLITE_ERROR, or SQLITE_MISUSE.**** SQLITE_BUSY means that the virtual machine attempted to open** a locked database and there is no busy callback registered.** Call sqlite_step() again to retry the open.  *pN is set to 0** and *pazColName and *pazValue are both set to NULL.**** SQLITE_DONE means that the virtual machine has finished** executing.  sqlite_step() should not be called again on this** virtual machine.  *pN and *pazColName are set appropriately** but *pazValue is set to NULL.**** SQLITE_ROW means that the virtual machine has generated another** row of the result set.  *pN is set to the number of columns in** the row.  *pazColName is set to the names of the columns followed** by the column datatypes.  *pazValue is set to the values of each** column in the row.  The value of the i-th column is (*pazValue)[i].** The name of the i-th column is (*pazColName)[i] and the datatype** of the i-th column is (*pazColName)[i+*pN].**** SQLITE_ERROR means that a run-time error (such as a constraint** violation) has occurred.  The details of the error will be returned** by the next call to sqlite_finalize().  sqlite_step() should not** be called again on the VM.**** SQLITE_MISUSE means that the this routine was called inappropriately.** Perhaps it was called on a virtual machine that had already been** finalized or on one that had previously returned SQLITE_ERROR or** SQLITE_DONE.  Or it could be the case the the same database connection** is being used simulataneously by two or more threads.*/int sqlite_step(  sqlite_vm *pVm,              /* The virtual machine to execute */  int *pN,                     /* OUT: Number of columns in result */  const char ***pazValue,      /* OUT: Column data */  const char ***pazColName     /* OUT: Column names and datatypes */){  Vdbe *p = (Vdbe*)pVm;  sqlite *db;  int rc;  if( p->magic!=VDBE_MAGIC_RUN ){    return SQLITE_MISUSE;  }  db = p->db;  if( sqliteSafetyOn(db) ){    p->rc = SQLITE_MISUSE;    return SQLITE_MISUSE;  }  if( p->explain ){    rc = sqliteVdbeList(p);  }else{    rc = sqliteVdbeExec(p);  }  if( rc==SQLITE_DONE || rc==SQLITE_ROW ){    if( pazColName ) *pazColName = (const char**)p->azColName;    if( pN ) *pN = p->nResColumn;  }else{    if( pazColName) *pazColName = 0;    if( pN ) *pN = 0;  }  if( pazValue ){    if( rc==SQLITE_ROW ){      *pazValue = (const char**)p->azResColumn;    }else{      *pazValue = 0;    }  }  if( sqliteSafetyOff(db) ){    return SQLITE_MISUSE;  }  return rc;}/*** Insert a new aggregate element and make it the element that** has focus.**** Return 0 on success and 1 if memory is exhausted.*/static int AggInsert(Agg *p, char *zKey, int nKey){  AggElem *pElem, *pOld;  int i;  Mem *pMem;  pElem = sqliteMalloc( sizeof(AggElem) + nKey +                        (p->nMem-1)*sizeof(pElem->aMem[0]) );  if( pElem==0 ) return 1;  pElem->zKey = (char*)&pElem->aMem[p->nMem];  memcpy(pElem->zKey, zKey, nKey);  pElem->nKey = nKey;  pOld = sqliteHashInsert(&p->hash, pElem->zKey, pElem->nKey, pElem);  if( pOld!=0 ){    assert( pOld==pElem );  /* Malloc failed on insert */    sqliteFree(pOld);    return 0;  }  for(i=0, pMem=pElem->aMem; i<p->nMem; i++, pMem++){    pMem->flags = MEM_Null;  }  p->pCurrent = pElem;  return 0;}/*** Get the AggElem currently in focus*/#define AggInFocus(P)   ((P).pCurrent ? (P).pCurrent : _AggInFocus(&(P)))static AggElem *_AggInFocus(Agg *p){  HashElem *pElem = sqliteHashFirst(&p->hash);  if( pElem==0 ){    AggInsert(p,"",1);    pElem = sqliteHashFirst(&p->hash);  }  return pElem ? sqliteHashData(pElem) : 0;}/*** Convert the given stack entity into a string if it isn't one** already.*/#define Stringify(P) if(((P)->flags & MEM_Str)==0){hardStringify(P);}static int hardStringify(Mem *pStack){  int fg = pStack->flags;  if( fg & MEM_Real ){    sqlite_snprintf(sizeof(pStack->zShort),pStack->zShort,"%.15g",pStack->r);  }else if( fg & MEM_Int ){    sqlite_snprintf(sizeof(pStack->zShort),pStack->zShort,"%d",pStack->i);  }else{    pStack->zShort[0] = 0;  }  pStack->z = pStack->zShort;  pStack->n = strlen(pStack->zShort)+1;  pStack->flags = MEM_Str | MEM_Short;  return 0;}/*** Convert the given stack entity into a string that has been obtained** from sqliteMalloc().  This is different from Stringify() above in that** Stringify() will use the NBFS bytes of static string space if the string** will fit but this routine always mallocs for space.** Return non-zero if we run out of memory.*/#define Dynamicify(P) (((P)->flags & MEM_Dyn)==0 ? hardDynamicify(P):0)static int hardDynamicify(Mem *pStack){  int fg = pStack->flags;  char *z;  if( (fg & MEM_Str)==0 ){    hardStringify(pStack);  }  assert( (fg & MEM_Dyn)==0 );  z = sqliteMallocRaw( pStack->n );  if( z==0 ) return 1;  memcpy(z, pStack->z, pStack->n);  pStack->z = z;  pStack->flags |= MEM_Dyn;  return 0;}/*** An ephemeral string value (signified by the MEM_Ephem flag) contains** a pointer to a dynamically allocated string where some other entity** is responsible for deallocating that string.  Because the stack entry** does not control the string, it might be deleted without the stack** entry knowing it.**** This routine converts an ephemeral string into a dynamically allocated** string that the stack entry itself controls.  In other words, it** converts an MEM_Ephem string into an MEM_Dyn string.*/#define Deephemeralize(P) \   if( ((P)->flags&MEM_Ephem)!=0 && hardDeephem(P) ){ goto no_mem;}static int hardDeephem(Mem *pStack){  char *z;  assert( (pStack->flags & MEM_Ephem)!=0 );  z = sqliteMallocRaw( pStack->n );  if( z==0 ) return 1;  memcpy(z, pStack->z, pStack->n);  pStack->z = z;  pStack->flags &= ~MEM_Ephem;  pStack->flags |= MEM_Dyn;  return 0;}/*** Release the memory associated with the given stack level.  This** leaves the Mem.flags field in an inconsistent state.*/#define Release(P) if((P)->flags&MEM_Dyn){ sqliteFree((P)->z); }/*** Pop the stack N times.*/static void popStack(Mem **ppTos, int N){  Mem *pTos = *ppTos;  while( N>0 ){    N--;    Release(pTos);    pTos--;  }  *ppTos = pTos;}/*** Return TRUE if zNum is a 32-bit signed integer and write** the value of the integer into *pNum.  If zNum is not an integer** or is an integer that is too large to be expressed with just 32** bits, then return false.**** Under Linux (RedHat 7.2) this routine is much faster than atoi()** for converting strings into integers.*/static int toInt(const char *zNum, int *pNum){  int v = 0;  int neg;  int i, c;  if( *zNum=='-' ){    neg = 1;    zNum++;  }else if( *zNum=='+' ){    neg = 0;    zNum++;  }else{    neg = 0;  }  for(i=0; (c=zNum[i])>='0' && c<='9'; i++){    v = v*10 + c - '0';  }  *pNum = neg ? -v : v;  return c==0 && i>0 && (i<10 || (i==10 && memcmp(zNum,"2147483647",10)<=0));}/*** Convert the given stack entity into a integer if it isn't one** already.**** Any prior string or real representation is invalidated.  ** NULLs are converted into 0.*/#define Integerify(P) if(((P)->flags&MEM_Int)==0){ hardIntegerify(P); }static void hardIntegerify(Mem *pStack){  if( pStack->flags & MEM_Real ){    pStack->i = (int)pStack->r;    Release(pStack);  }else if( pStack->flags & MEM_Str ){    toInt(pStack->z, &pStack->i);    Release(pStack);  }else{    pStack->i = 0;  }  pStack->flags = MEM_Int;}/*** Get a valid Real representation for the given stack element.**** Any prior string or integer representation is retained.** NULLs are converted into 0.0.*/#define Realify(P) if(((P)->flags&MEM_Real)==0){ hardRealify(P); }static void hardRealify(Mem *pStack){  if( pStack->flags & MEM_Str ){    pStack->r = sqliteAtoF(pStack->z, 0);  }else if( pStack->flags & MEM_Int ){    pStack->r = pStack->i;  }else{    pStack->r = 0.0;  }  pStack->flags |= MEM_Real;}/*** The parameters are pointers to the head of two sorted lists** of Sorter structures.  Merge these two lists together and return** a single sorted list.  This routine forms the core of the merge-sort** algorithm.**** In the case of a tie, left sorts in front of right.*/static Sorter *Merge(Sorter *pLeft, Sorter *pRight){  Sorter sHead;  Sorter *pTail;  pTail = &sHead;  pTail->pNext = 0;  while( pLeft && pRight ){    int c = sqliteSortCompare(pLeft->zKey, pRight->zKey);    if( c<=0 ){      pTail->pNext = pLeft;      pLeft = pLeft->pNext;    }else{      pTail->pNext = pRight;      pRight = pRight->pNext;    }    pTail = pTail->pNext;  }  if( pLeft ){    pTail->pNext = pLeft;  }else if( pRight ){    pTail->pNext = pRight;  }  return sHead.pNext;}/*** The following routine works like a replacement for the standard** library routine fgets().  The difference is in how end-of-line (EOL)** is handled.  Standard fgets() uses LF for EOL under unix, CRLF** under windows, and CR under mac.  This routine accepts any of these** character sequences as an EOL mark.  The EOL mark is replaced by** a single LF character in zBuf.*/static char *vdbe_fgets(char *zBuf, int nBuf, FILE *in){  int i, c;  for(i=0; i<nBuf-1 && (c=getc(in))!=EOF; i++){    zBuf[i] = c;    if( c=='\r' || c=='\n' ){      if( c=='\r' ){        zBuf[i] = '\n';        c = getc(in);        if( c!=EOF && c!='\n' ) ungetc(c, in);      }      i++;      break;    }  }  zBuf[i]  = 0;  return i>0 ? zBuf : 0;}/*** Make sure there is space in the Vdbe structure to hold at least** mxCursor cursors.  If there is not currently enough space, then** allocate more.**** If a memory allocation error occurs, return 1.  Return 0 if** everything works.*/static int expandCursorArraySize(Vdbe *p, int mxCursor){  if( mxCursor>=p->nCursor ){    Cursor *aCsr = sqliteRealloc( p->aCsr, (mxCursor+1)*sizeof(Cursor) );    if( aCsr==0 ) return 1;    p->aCsr = aCsr;    memset(&p->aCsr[p->nCursor], 0, sizeof(Cursor)*(mxCursor+1-p->nCursor));    p->nCursor = mxCursor+1;  }  return 0;}#ifdef VDBE_PROFILE/*** The following routine only works on pentium-class processors.** It uses the RDTSC opcode to read cycle count value out of the** processor and returns that value.  This can be used for high-res** profiling.*/