/*

** 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 "sqlite3_stmt*" 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 sqlite3VdbeExec()

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

*/

#include "sqliteInt.h"

#include "os.h"

#include <ctype.h>

#include <math.h>

#include "vdbeInt.h"

/*

** The following global variable is incremented every time a cursor

** moves, either by the OP_MoveXX, OP_Next, or OP_Prev opcodes.  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.

*/

#ifdef SQLITE_TEST

int sqlite3_search_count = 0;

#endif

/*

** When this global variable is positive, it gets decremented once before

** each instruction in the VDBE.  When reaches zero, the u1.isInterrupted

** field of the sqlite3 structure is set in order to simulate and interrupt.

**

** This facility is used for testing purposes only.  It does not function

** in an ordinary build.

*/

#ifdef SQLITE_TEST

int sqlite3_interrupt_count = 0;

#endif

/*

** The next global variable is incremented each type the OP_Sort opcode

** is executed.  The test procedures use this information to make sure that

** sorting is occurring or not occuring at appropriate times.   This variable

** has no function other than to help verify the correct operation of the

** library.

*/

#ifdef SQLITE_TEST

int sqlite3_sort_count = 0;

#endif

/*

** The next global variable records the size of the largest MEM_Blob

** or MEM_Str that has appeared on the VDBE stack.  The test procedures

** use this information to make sure that the zero-blob functionality

** is working correctly.   This variable has no function other than to

** help verify the correct operation of the library.

*/

#ifdef SQLITE_TEST

int sqlite3_max_blobsize = 0;

#endif

/*

** 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){ sqlite3VdbeMemRelease(P); }

/*

** Convert the given stack entity into a string if it isn't one

** already. Return non-zero if a malloc() fails.

*/

#define Stringify(P, enc) \

   if(((P)->flags&(MEM_Str|MEM_Blob))==0 && sqlite3VdbeMemStringify(P,enc)) \

     { goto no_mem; }

/*

** 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,enc) sqlite3VdbeMemDynamicify(P)

/*

** The header of a record consists of a sequence variable-length integers.

** These integers are almost always small and are encoded as a single byte.

** The following macro takes advantage this fact to provide a fast decode

** of the integers in a record header.  It is faster for the common case

** where the integer is a single byte.  It is a little slower when the

** integer is two or more bytes.  But overall it is faster.

**

** The following expressions are equivalent:

**

**     x = sqlite3GetVarint32( A, &B );

**

**     x = GetVarint( A, B );

**

*/

#define GetVarint(A,B)  ((B = *(A))<=0x7f ? 1 : sqlite3GetVarint32(A, &B))

/*

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

       && sqlite3VdbeMemMakeWriteable(P) ){ goto no_mem;}

/*

** Call sqlite3VdbeMemExpandBlob() on the supplied value (type Mem*)

** P if required.

*/

#define ExpandBlob(P) (((P)->flags&MEM_Zero)?sqlite3VdbeMemExpandBlob(P):0)

/*

** Argument pMem points at a memory cell that will be passed to a

** user-defined function or returned to the user as the result of a query.

** The second argument, 'db_enc' is the text encoding used by the vdbe for

** stack variables.  This routine sets the pMem->enc and pMem->type

** variables used by the sqlite3_value_*() routines.

*/

#define storeTypeInfo(A,B) _storeTypeInfo(A)

static void _storeTypeInfo(Mem *pMem){

  int flags = pMem->flags;

  if( flags & MEM_Null ){

    pMem->type = SQLITE_NULL;

  }

  else if( flags & MEM_Int ){

    pMem->type = SQLITE_INTEGER;

  }

  else if( flags & MEM_Real ){

    pMem->type = SQLITE_FLOAT;

  }

  else if( flags & MEM_Str ){

    pMem->type = SQLITE_TEXT;

  }else{

    pMem->type = SQLITE_BLOB;

  }

}

/*

** Pop the stack N times.

*/

static void popStack(Mem **ppTos, int N){

  Mem *pTos = *ppTos;

  while( N>0 ){

    N--;

    Release(pTos);

    pTos--;

  }

  *ppTos = pTos;

}

/*

** Allocate cursor number iCur.  Return a pointer to it.  Return NULL

** if we run out of memory.

*/

static Cursor *allocateCursor(Vdbe *p, int iCur, int iDb){

  Cursor *pCx;

  assert( iCur<p->nCursor );

  if( p->apCsr[iCur] ){

    sqlite3VdbeFreeCursor(p, p->apCsr[iCur]);

  }

  p->apCsr[iCur] = pCx = sqliteMalloc( sizeof(Cursor) );

  if( pCx ){

    pCx->iDb = iDb;

  }

  return pCx;

}

/*

** Try to convert a value into a numeric representation if we can

** do so without loss of information.  In other words, if the string

** looks like a number, convert it into a number.  If it does not

** look like a number, leave it alone.

*/

static void applyNumericAffinity(Mem *pRec){

  if( (pRec->flags & (MEM_Real|MEM_Int))==0 ){

    int realnum;

    sqlite3VdbeMemNulTerminate(pRec);

    if( (pRec->flags&MEM_Str)

         && sqlite3IsNumber(pRec->z, &realnum, pRec->enc) ){

      i64 value;

      sqlite3VdbeChangeEncoding(pRec, SQLITE_UTF8);

      if( !realnum && sqlite3Atoi64(pRec->z, &value) ){

        sqlite3VdbeMemRelease(pRec);

        pRec->u.i = value;

        pRec->flags = MEM_Int;

      }else{

        sqlite3VdbeMemRealify(pRec);

      }

    }

  }

}

/*

** Processing is determine by the affinity parameter:

**

** SQLITE_AFF_INTEGER:

** SQLITE_AFF_REAL:

** SQLITE_AFF_NUMERIC:

**    Try to convert pRec to an integer representation or a 

**    floating-point representation if an integer representation

**    is not possible.  Note that the integer representation is

**    always preferred, even if the affinity is REAL, because

**    an integer representation is more space efficient on disk.

**

** SQLITE_AFF_TEXT:

**    Convert pRec to a text representation.

**

** SQLITE_AFF_NONE:

**    No-op.  pRec is unchanged.

*/

static void applyAffinity(Mem *pRec, char affinity, u8 enc){

  if( affinity==SQLITE_AFF_TEXT ){

    /* Only attempt the conversion to TEXT if there is an integer or real

    ** representation (blob and NULL do not get converted) but no string

    ** representation.

    */

    if( 0==(pRec->flags&MEM_Str) && (pRec->flags&(MEM_Real|MEM_Int)) ){

      sqlite3VdbeMemStringify(pRec, enc);

    }

    pRec->flags &= ~(MEM_Real|MEM_Int);

  }else if( affinity!=SQLITE_AFF_NONE ){

    assert( affinity==SQLITE_AFF_INTEGER || affinity==SQLITE_AFF_REAL

             || affinity==SQLITE_AFF_NUMERIC );

    applyNumericAffinity(pRec);

    if( pRec->flags & MEM_Real ){

      sqlite3VdbeIntegerAffinity(pRec);

    }

  }

}

/*

** Try to convert the type of a function argument or a result column

** into a numeric representation.  Use either INTEGER or REAL whichever

** is appropriate.  But only do the conversion if it is possible without

** loss of information and return the revised type of the argument.

**

** This is an EXPERIMENTAL api and is subject to change or removal.

*/

int sqlite3_value_numeric_type(sqlite3_value *pVal){

  Mem *pMem = (Mem*)pVal;

  applyNumericAffinity(pMem);

  storeTypeInfo(pMem, 0);

  return pMem->type;

}

/*

** Exported version of applyAffinity(). This one works on sqlite3_value*, 

** not the internal Mem* type.

*/

void sqlite3ValueApplyAffinity(sqlite3_value *pVal, u8 affinity, u8 enc){

  applyAffinity((Mem *)pVal, affinity, enc);

}

#ifdef SQLITE_DEBUG

/*

** Write a nice string representation of the contents of cell pMem

** into buffer zBuf, length nBuf.

*/

void sqlite3VdbeMemPrettyPrint(Mem *pMem, char *zBuf){

  char *zCsr = zBuf;

  int f = pMem->flags;

  static const char *const encnames[] = {"(X)", "(8)", "(16LE)", "(16BE)"};

  if( f&MEM_Blob ){

    int i;

    char c;

    if( f & MEM_Dyn ){

      c = 'z';

      assert( (f & (MEM_Static|MEM_Ephem))==0 );

    }else if( f & MEM_Static ){

      c = 't';

      assert( (f & (MEM_Dyn|MEM_Ephem))==0 );

    }else if( f & MEM_Ephem ){

      c = 'e';

      assert( (f & (MEM_Static|MEM_Dyn))==0 );

    }else{

      c = 's';

    }

    sqlite3_snprintf(100, zCsr, "%c", c);

    zCsr += strlen(zCsr);

    sqlite3_snprintf(100, zCsr, "%d[", pMem->n);

    zCsr += strlen(zCsr);

    for(i=0; i<16 && i<pMem->n; i++){

      sqlite3_snprintf(100, zCsr, "%02X", ((int)pMem->z[i] & 0xFF));

      zCsr += strlen(zCsr);

    }

    for(i=0; i<16 && i<pMem->n; i++){

      char z = pMem->z[i];

      if( z<32 || z>126 ) *zCsr++ = '.';

      else *zCsr++ = z;

    }

    sqlite3_snprintf(100, zCsr, "]%s", encnames[pMem->enc]);

    zCsr += strlen(zCsr);

    if( f & MEM_Zero ){

      sqlite3_snprintf(100, zCsr,"+%lldz",pMem->u.i);

      zCsr += strlen(zCsr);

    }

    *zCsr = '\0';

  }else if( f & MEM_Str ){

    int j, k;

    zBuf[0] = ' ';

    if( f & MEM_Dyn ){

      zBuf[1] = 'z';

      assert( (f & (MEM_Static|MEM_Ephem))==0 );

    }else if( f & MEM_Static ){

      zBuf[1] = 't';

      assert( (f & (MEM_Dyn|MEM_Ephem))==0 );

    }else if( f & MEM_Ephem ){

      zBuf[1] = 'e';

      assert( (f & (MEM_Static|MEM_Dyn))==0 );

    }else{

      zBuf[1] = 's';

    }

    k = 2;

    sqlite3_snprintf(100, &zBuf[k], "%d", pMem->n);

    k += strlen(&zBuf[k]);

    zBuf[k++] = '[';

    for(j=0; j<15 && j<pMem->n; j++){

      u8 c = pMem->z[j];

      if( c>=0x20 && c<0x7f ){

        zBuf[k++] = c;

      }else{

        zBuf[k++] = '.';

      }

    }

    zBuf[k++] = ']';

    sqlite3_snprintf(100,&zBuf[k], encnames[pMem->enc]);

    k += strlen(&zBuf[k]);

    zBuf[k++] = 0;

  }

}

#endif

#ifdef VDBE_PROFILE

/*

** The following routine only works on pentium-class processors.

** It uses the RDTSC opcode to read the cycle count value out of the

** processor and returns that value.  This can be used for high-res

** profiling.

*/

__inline__ unsigned long long int hwtime(void){

  unsigned long long int x;

  __asm__("rdtsc\n\t"

          "mov %%edx, %%ecx\n\t"

          :"=A" (x));

  return x;

}

#endif

/*

** The CHECK_FOR_INTERRUPT macro defined here looks to see if the

** sqlite3_interrupt() routine has been called.  If it has been, then

** processing of the VDBE program is interrupted.

**

** This macro added to every instruction that does a jump in order to

** implement a loop.  This test used to be on every single instruction,

** but that meant we more testing that we needed.  By only testing the

** flag on jump instructions, we get a (small) speed improvement.

*/

#define CHECK_FOR_INTERRUPT \

   if( db->u1.isInterrupted ) goto abort_due_to_interrupt;

/*

** Execute as much of a VDBE program as we can then return.

**

** sqlite3VdbeMakeReady() must be called before this routine in order to

** close the program with a final OP_Halt and to set up the callbacks

** and the error message pointer.

**

** Whenever a row or result data is available, this routine will either

** invoke the result callback (if there is one) or return with

** SQLITE_ROW.

**

** If an attempt is made to open a locked database, then this routine

** will either invoke the busy callback (if there is one) or it will

** return SQLITE_BUSY.

**

** If an error occurs, an error message is written to memory obtained

** from sqliteMalloc() and p->zErrMsg is made to point to that memory.

** The error code is stored in p->rc and this routine returns SQLITE_ERROR.

**

** If the callback ever returns non-zero, then the program exits

** immediately.  There will be no error message but the p->rc field is

** set to SQLITE_ABORT and this routine will return SQLITE_ERROR.

**

** A memory allocation error causes p->rc to be set to SQLITE_NOMEM and this

** routine to return SQLITE_ERROR.

**

** Other fatal errors return SQLITE_ERROR.

**

** After this routine has finished, sqlite3VdbeFinalize() should be

** used to clean up the mess that was left behind.

*/

int sqlite3VdbeExec(

  Vdbe *p                    /* The VDBE */

){

  int pc;                    /* The program counter */

  Op *pOp;                   /* Current operation */

  int rc = SQLITE_OK;        /* Value to return */

  sqlite3 *db = p->db;       /* The database */

  u8 encoding = ENC(db);     /* The database encoding */

  Mem *pTos;                 /* Top entry in the operand stack */

#ifdef VDBE_PROFILE

  unsigned long long start;  /* CPU clock count at start of opcode */

  int origPc;                /* Program counter at start of opcode */

#endif

#ifndef SQLITE_OMIT_PROGRESS_CALLBACK

  int nProgressOps = 0;      /* Opcodes executed since progress callback. */

#endif

#ifndef NDEBUG

  Mem *pStackLimit;

#endif

  if( p->magic!=VDBE_MAGIC_RUN ) return SQLITE_MISUSE;

  assert( db->magic==SQLITE_MAGIC_BUSY );

  pTos = p->pTos;

  if( p->rc==SQLITE_NOMEM ){

    /* This happens if a malloc() inside a call to sqlite3_column_text() or

    ** sqlite3_column_text16() failed.  */

    goto no_mem;

  }

  assert( p->rc==SQLITE_OK || p->rc==SQLITE_BUSY );

  p->rc = SQLITE_OK;

  assert( p->explain==0 );

  if( p->popStack ){

    popStack(&pTos, p->popStack);

    p->popStack = 0;

  }

  p->resOnStack = 0;

  db->busyHandler.nBusy = 0;

  CHECK_FOR_INTERRUPT;

  sqlite3VdbeIOTraceSql(p);

#ifdef SQLITE_DEBUG

  if( (p->db->flags & SQLITE_VdbeListing)!=0

    || sqlite3OsFileExists("vdbe_explain")

  ){

    int i;

    printf("VDBE Program Listing:\n");

    sqlite3VdbePrintSql(p);

    for(i=0; i<p->nOp; i++){

      sqlite3VdbePrintOp(stdout, i, &p->aOp[i]);

    }

  }

  if( sqlite3OsFileExists("vdbe_trace") ){

    p->trace = stdout;

  }

#endif

  for(pc=p->pc; rc==SQLITE_OK; pc++){

    assert( pc>=0 && pc<p->nOp );

    assert( pTos<=&p->aStack[pc] );

    if( sqlite3MallocFailed() ) goto no_mem;

#ifdef VDBE_PROFILE

    origPc = pc;

    start = hwtime();

#endif

    pOp = &p->aOp[pc];

    /* Only allow tracing if SQLITE_DEBUG is defined.

    */

#ifdef SQLITE_DEBUG

    if( p->trace ){

      if( pc==0 ){

        printf("VDBE Execution Trace:\n");

        sqlite3VdbePrintSql(p);

      }

      sqlite3VdbePrintOp(p->trace, pc, pOp);

    }

    if( p->trace==0 && pc==0 && sqlite3OsFileExists("vdbe_sqltrace") ){

      sqlite3VdbePrintSql(p);

    }

#endif

    /* Check to see if we need to simulate an interrupt.  This only happens

    ** if we have a special test build.

    */

#ifdef SQLITE_TEST

    if( sqlite3_interrupt_count>0 ){

      sqlite3_interrupt_count--;

      if( sqlite3_interrupt_count==0 ){

        sqlite3_interrupt(db);

      }

    }

#endif

#ifndef SQLITE_OMIT_PROGRESS_CALLBACK

    /* Call the progress callback if it is configured and the required number

    ** of VDBE ops have been executed (either since this invocation of

    ** sqlite3VdbeExec() or since last time the progress callback was called).

    ** If the progress callback returns non-zero, exit the virtual machine with

    ** a return code SQLITE_ABORT.

    */

    if( db->xProgress ){

      if( db->nProgressOps==nProgressOps ){

        int prc;

        if( sqlite3SafetyOff(db) ) goto abort_due_to_misuse;

        prc =db->xProgress(db->pProgressArg);

        if( sqlite3SafetyOn(db) ) goto abort_due_to_misuse;

        if( prc!=0 ){

          rc = SQLITE_INTERRUPT;

          goto vdbe_halt;

        }

        nProgressOps = 0;

      }

      nProgressOps++;

    }

#endif

#ifndef NDEBUG

    /* This is to check that the return value of static function

    ** opcodeNoPush() (see vdbeaux.c) returns values that match the

    ** implementation of the virtual machine in this file. If

    ** opcodeNoPush() returns non-zero, then the stack is guarenteed

    ** not to grow when the opcode is executed. If it returns zero, then

    ** the stack may grow by at most 1.

    **

    ** The global wrapper function sqlite3VdbeOpcodeUsesStack() is not 

    ** available if NDEBUG is defined at build time.

    */ 

    pStackLimit = pTos;

    if( !sqlite3VdbeOpcodeNoPush(pOp->opcode) ){

      pStackLimit++;

    }

#endif

    switch( pOp->opcode ){

/*****************************************************************************

** What follows is a massive switch statement where each case implements a

** separate instruction in the virtual machine.  If we follow the usual

** indentation conventions, each case should be indented by 6 spaces.  But

** that is a lot of wasted space on the left margin.  So the code within

** the switch statement will break with convention and be flush-left. Another

** big comment (similar to this one) will mark the point in the code where

** we transition back to normal indentation.

**

** The formatting of each case is important.  The makefile for SQLite

** generates two C files "opcodes.h" and "opcodes.c" by scanning this

** file looking for lines that begin with "case OP_".  The opcodes.h files

** will be filled with #defines that give unique integer values to each

** opcode and the opcodes.c file is filled with an array of strings where

** each string is the symbolic name for the corresponding opcode.  If the

** case statement is followed by a comment of the form "/# same as ... #/"

** that comment is used to determine the particular value of the opcode.

**

** If a comment on the same line as the "case OP_" construction contains

** the word "no-push", then the opcode is guarenteed not to grow the 

** vdbe stack when it is executed. See function opcode() in

** vdbeaux.c for details.

**

** Documentation about VDBE opcodes is generated by scanning this file

** for lines of that contain "Opcode:".  That line and all subsequent

** comment lines are used in the generation of the opcode.html documentation

** file.

**

** SUMMARY:

**

**     Formatting is important to scripts that scan this file.

**     Do not deviate from the formatting style currently in use.

**

*****************************************************************************/

/* Opcode:  Goto * P2 *

**

** An unconditional jump to address P2.

** The next instruction executed will be 

** the one at index P2 from the beginning of

** the program.

*/

case OP_Goto: {             /* no-push */

  CHECK_FOR_INTERRUPT;

  pc = pOp->p2 - 1;

  break;

}

/* Opcode:  Gosub * P2 *

**

** Push the current address plus 1 onto the return address stack

** and then jump to address P2.

**

** The return address stack is of limited depth.  If too many

** OP_Gosub operations occur without intervening OP_Returns, then

** the return address stack will fill up and processing will abort

** with a fatal error.

*/

case OP_Gosub: {            /* no-push */

  assert( p->returnDepth<sizeof(p->returnStack)/sizeof(p->returnStack[0]) );

  p->returnStack[p->returnDepth++] = pc+1;

  pc = pOp->p2 - 1;

  break;

}

/* Opcode:  Return * * *

**

** Jump immediately to the next instruction after the last unreturned

** OP_Gosub.  If an OP_Return has occurred for all OP_Gosubs, then

** processing aborts with a fatal error.

*/

case OP_Return: {           /* no-push */