SQLite

**
*************************************************************************
** Main file for the SQLite library.  The routines in this file
** implement the programmer interface to the library.  Routines in
** other files are for internal use by SQLite and should not be
** accessed by users of the library.
**
** $Id: main.c,v 1.515 2008/12/08 21:37:15 drh Exp $
*/
#include "sqliteInt.h"
#include <ctype.h>

#ifdef SQLITE_ENABLE_FTS3
# include "fts3.h"
#endif
#ifdef SQLITE_ENABLE_RTREE
# include "rtree.h"
#endif
#ifdef SQLITE_ENABLE_ICU
# include "sqliteicu.h"
#endif

/*
** The version of the library
*/
#ifndef SQLITE_AMALGAMATION
const char sqlite3_version[] = SQLITE_VERSION;
#endif
const char *sqlite3_libversion(void){ return sqlite3_version; }
int sqlite3_libversion_number(void){ return SQLITE_VERSION_NUMBER; }
int sqlite3_threadsafe(void){ return SQLITE_THREADSAFE; }

#if !defined(SQLITE_OMIT_TRACE) && defined(SQLITE_ENABLE_IOTRACE)
/*
** If the following function pointer is not NULL and if

/*
** 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.
**
*************************************************************************
** Internal interface definitions for SQLite.
**
** @(#) $Id: sqliteInt.h,v 1.805 2008/12/08 21:37:15 drh Exp $
*/
#ifndef _SQLITEINT_H_
#define _SQLITEINT_H_

/*
** Include the configuration header output by 'configure' if we're using the
** autoconf-based build

typedef INT8_TYPE i8;              /* 1-byte signed integer */

/*
** Macros to determine whether the machine is big or little endian,
** evaluated at runtime.
*/
#ifdef SQLITE_AMALGAMATION
const int sqlite3one = 1;
#else
extern const int sqlite3one;
#endif
#if defined(i386) || defined(__i386__) || defined(_M_IX86)\
                             || defined(__x86_64) || defined(__x86_64__)
# define SQLITE_BIGENDIAN    0
# define SQLITE_LITTLEENDIAN 1

  int iFrom;            /* Which entry in the FROM clause */
  int wsFlags;          /* "Where-Scan" flags show the choosen scan strategy */
  int iMem;             /* First memory cell used by this level */
  int iLeftJoin;        /* Memory cell used to implement LEFT OUTER JOIN */
  Index *pIdx;          /* Index used.  NULL if no index */
  int iTabCur;          /* The VDBE cursor used to access the table */
  int iIdxCur;          /* The VDBE cursor used to access pIdx */
  int addrBrk;          /* Jump here to break out of the loop */
  int addrNxt;          /* Jump here to start the next IN combination */
  int addrCont;         /* Jump here to continue with the next loop cycle */
  int addrFirst;        /* First instruction of interior of the loop */
  int op, p1, p2, p5;   /* Opcode used to terminate the loop */
  int nEq;              /* Number of == or IN constraints on this loop */
  int nIn;              /* Number of IN operators constraining this loop */
  struct InLoop {
    int iCur;              /* The VDBE cursor used by this IN operator */
    int addrInTop;         /* Top of the IN loop */
  } *aInLoop;           /* Information about each nested IN operator */
  sqlite3_index_info *pBestIdx;  /* Index information for this level */

  /* The following field is really not part of the current level.  But
  ** we need a place to cache index information for each table in the
  ** FROM clause and the WhereLevel structure is a convenient place.
  */

**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** This file contains routines used to translate between UTF-8, 
** UTF-16, UTF-16BE, and UTF-16LE.
**
** $Id: utf.c,v 1.67 2008/12/08 21:37:15 drh Exp $
**
** Notes on UTF-8:
**
**   Byte-0    Byte-1    Byte-2    Byte-3    Value
**  0xxxxxxx                                 00000000 00000000 0xxxxxxx
**  110yyyyy  10xxxxxx                       00000000 00000yyy yyxxxxxx
**  1110zzzz  10yyyyyy  10xxxxxx             00000000 zzzzyyyy yyxxxxxx

**     0xfe 0xff   big-endian utf-16 follows
**
*/
#include "sqliteInt.h"
#include <assert.h>
#include "vdbeInt.h"

#ifndef SQLITE_AMALGAMATION
/*
** The following constant value is used by the SQLITE_BIGENDIAN and
** SQLITE_LITTLEENDIAN macros.
*/
const int sqlite3one = 1;
#endif /* SQLITE_AMALGAMATION */

/*
** This lookup table is used to help decode the first byte of
** a multi-byte UTF8 character.
*/
static const unsigned char sqlite3UtfTrans1[] = {
  0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,

** This module contains C code that generates VDBE code used to process
** the WHERE clause of SQL statements.  This module is responsible for
** generating the code that loops through a table looking for applicable
** rows.  Indices are selected and used to speed the search when doing
** so is applicable.  Because this module is responsible for selecting
** indices, you might also think of this module as the "query optimizer".
**
** $Id: where.c,v 1.334 2008/12/08 21:37:16 drh Exp $
*/
#include "sqliteInt.h"

/*
** Trace output macros
*/
#if defined(SQLITE_TEST) || defined(SQLITE_DEBUG)

** This is true even if this routine fails to allocate a new WhereTerm.
**
** WARNING:  This routine might reallocate the space used to store
** WhereTerms.  All pointers to WhereTerms should be invalidated after
** calling this routine.  Such pointers may be reinitialized by referencing
** the pWC->a[] array.
*/
static int whereClauseInsert(WhereClause *pWC, Expr *p, u16 wtFlags){
  WhereTerm *pTerm;
  int idx;
  if( pWC->nTerm>=pWC->nSlot ){
    WhereTerm *pOld = pWC->a;
    sqlite3 *db = pWC->pParse->db;
    pWC->a = sqlite3DbMallocRaw(db, sizeof(pWC->a[0])*pWC->nSlot*2 );
    if( pWC->a==0 ){

    assert( pX->op==TK_IN );
    iReg = iTarget;
    eType = sqlite3FindInIndex(pParse, pX, 0);
    iTab = pX->iTable;
    sqlite3VdbeAddOp2(v, OP_Rewind, iTab, 0);
    VdbeComment((v, "%.*s", pX->span.n, pX->span.z));
    if( pLevel->nIn==0 ){
      pLevel->addrNxt = sqlite3VdbeMakeLabel(v);
    }
    pLevel->nIn++;
    pLevel->aInLoop = sqlite3DbReallocOrFree(pParse->db, pLevel->aInLoop,
                                    sizeof(pLevel->aInLoop[0])*pLevel->nIn);
    pIn = pLevel->aInLoop;
    if( pIn ){
      pIn += pLevel->nIn - 1;
      pIn->iCur = iTab;
      if( eType==IN_INDEX_ROWID ){
        pIn->addrInTop = sqlite3VdbeAddOp2(v, OP_Rowid, iTab, iReg);
      }else{
        pIn->addrInTop = sqlite3VdbeAddOp3(v, OP_Column, iTab, 0, iReg);
      }
      sqlite3VdbeAddOp1(v, OP_IsNull, iReg);
    }else{
      pLevel->nIn = 0;
    }
#endif
  }

    r1 = codeEqualityTerm(pParse, pTerm, pLevel, regBase+j);
    if( r1!=regBase+j ){
      sqlite3VdbeAddOp2(v, OP_SCopy, r1, regBase+j);
    }
    testcase( pTerm->eOperator & WO_ISNULL );
    testcase( pTerm->eOperator & WO_IN );
    if( (pTerm->eOperator & (WO_ISNULL|WO_IN))==0 ){
      sqlite3VdbeAddOp2(v, OP_IsNull, regBase+j, pLevel->addrBrk);
    }
  }
  return regBase;
}

#if defined(SQLITE_TEST)
/*

  Expr *pWhere,         /* The WHERE clause */
  ExprList **ppOrderBy, /* An ORDER BY clause, or NULL */
  u8 wctrlFlags         /* One of the WHERE_* flags defined in sqliteInt.h */
){
  int i;                     /* Loop counter */
  WhereInfo *pWInfo;         /* Will become the return value of this function */
  Vdbe *v = pParse->pVdbe;   /* The virtual database engine */
  int addrBrk, addrCont = 0; /* Addresses used during code generation */
  Bitmask notReady;          /* Cursors that are not yet positioned */
  WhereTerm *pTerm;          /* A single term in the WHERE clause */
  ExprMaskSet maskSet;       /* The expression mask set */
  WhereClause wc;            /* The WHERE clause is divided into these terms */
  struct SrcList_item *pTabItem;  /* A single entry from pTabList */
  WhereLevel *pLevel;             /* A single level in the pWInfo list */
  int iFrom;                      /* First unused FROM clause element */

  ** program.
  */
  notReady = ~(Bitmask)0;
  for(i=0, pLevel=pWInfo->a; i<pTabList->nSrc; i++, pLevel++){
    int j, k;
    int iCur = pTabItem->iCursor;  /* The VDBE cursor for the table */
    Index *pIdx;       /* The index we will be using */
    int addrNxt;           /* Where to jump to continue with the next IN case */
    int iIdxCur;       /* The VDBE cursor for the index */
    int omitTable;     /* True if we use the index only */
    int bRev;          /* True if we need to scan in reverse order */

    pTabItem = &pTabList->a[pLevel->iFrom];
    iCur = pTabItem->iCursor;
    pIdx = pLevel->pIdx;
    iIdxCur = pLevel->iIdxCur;
    bRev = (pLevel->wsFlags & WHERE_REVERSE)!=0;
    omitTable = (pLevel->wsFlags & WHERE_IDX_ONLY)!=0;

    /* Create labels for the "break" and "continue" instructions
    ** for the current loop.  Jump to addrBrk to break out of a loop.
    ** Jump to cont to go immediately to the next iteration of the
    ** loop.
    **
    ** When there is an IN operator, we also have a "addrNxt" label that
    ** means to continue with the next IN value combination.  When
    ** there are no IN operators in the constraints, the "addrNxt" label
    ** is the same as "addrBrk".
    */
    addrBrk = pLevel->addrBrk = pLevel->addrNxt = sqlite3VdbeMakeLabel(v);
    addrCont = pLevel->addrCont = sqlite3VdbeMakeLabel(v);

    /* If this is the right table of a LEFT OUTER JOIN, allocate and
    ** initialize a memory cell that records if this table matches any
    ** row of the left table of the join.
    */
    if( pLevel->iFrom>0 && (pTabItem[0].jointype & JT_LEFT)!=0 ){
      pLevel->iLeftJoin = ++pParse->nMem;

        }
        if( k==nConstraint ) break;
      }
      assert( pParse->disableColCache );
      pParse->disableColCache--;
      sqlite3VdbeAddOp2(v, OP_Integer, pBestIdx->idxNum, iReg);
      sqlite3VdbeAddOp2(v, OP_Integer, j-1, iReg+1);
      sqlite3VdbeAddOp4(v, OP_VFilter, iCur, addrBrk, iReg, pBestIdx->idxStr,
                        pBestIdx->needToFreeIdxStr ? P4_MPRINTF : P4_STATIC);
      sqlite3ReleaseTempRange(pParse, iReg, nConstraint+2);
      pBestIdx->needToFreeIdxStr = 0;
      for(j=0; j<nConstraint; j++){
        if( aUsage[j].omit ){
          int iTerm = aConstraint[j].iTermOffset;
          disableTerm(pLevel, &wc.a[iTerm]);

      int rtmp = sqlite3GetTempReg(pParse);
      pTerm = findTerm(&wc, iCur, -1, notReady, WO_EQ|WO_IN, 0);
      assert( pTerm!=0 );
      assert( pTerm->pExpr!=0 );
      assert( pTerm->leftCursor==iCur );
      assert( omitTable==0 );
      r1 = codeEqualityTerm(pParse, pTerm, pLevel, rtmp);
      addrNxt = pLevel->addrNxt;
      sqlite3VdbeAddOp2(v, OP_MustBeInt, r1, addrNxt);
      sqlite3VdbeAddOp3(v, OP_NotExists, iCur, addrNxt, r1);
      sqlite3ReleaseTempReg(pParse, rtmp);
      VdbeComment((v, "pk"));
      pLevel->op = OP_Noop;
    }else if( pLevel->wsFlags & WHERE_ROWID_RANGE ){
      /* Case 2:  We have an inequality comparison against the ROWID field.
      */
      int testOp = OP_Noop;

        ** reason we need to make sure that register r1 is really a newly
        ** allocated temporary register, and not part of the column-cache.
        ** For this reason we cannot use sqlite3ExprCodeTemp() here.
        */
        r1 = sqlite3GetTempReg(pParse);
        sqlite3ExprCode(pParse, pX->pRight, r1);

        sqlite3VdbeAddOp3(v, OP_ForceInt, r1, addrBrk, 
                             pX->op==TK_LE || pX->op==TK_GT);
        sqlite3VdbeAddOp3(v, bRev ? OP_MoveLt : OP_MoveGe, iCur, addrBrk, r1);
        VdbeComment((v, "pk"));
        sqlite3ReleaseTempReg(pParse, r1);
        disableTerm(pLevel, pStart);
      }else{
        sqlite3VdbeAddOp2(v, bRev ? OP_Last : OP_Rewind, iCur, addrBrk);
      }
      if( pEnd ){
        Expr *pX;
        pX = pEnd->pExpr;
        assert( pX!=0 );
        assert( pEnd->leftCursor==iCur );
        pLevel->iMem = ++pParse->nMem;

      pLevel->op = bRev ? OP_Prev : OP_Next;
      pLevel->p1 = iCur;
      pLevel->p2 = start;
      if( testOp!=OP_Noop ){
        int r1 = sqlite3GetTempReg(pParse);
        sqlite3VdbeAddOp2(v, OP_Rowid, iCur, r1);
        /* sqlite3VdbeAddOp2(v, OP_SCopy, pLevel->iMem, 0); */
        sqlite3VdbeAddOp3(v, testOp, pLevel->iMem, addrBrk, r1);
        sqlite3VdbeChangeP5(v, SQLITE_AFF_NUMERIC | SQLITE_JUMPIFNULL);
        sqlite3ReleaseTempReg(pParse, r1);
      }
    }else if( pLevel->wsFlags & (WHERE_COLUMN_RANGE|WHERE_COLUMN_EQ) ){
      /* Case 3: A scan using an index.
      **
      **         The WHERE clause may contain zero or more equality 

      int op;

      /* Generate code to evaluate all constraint terms using == or IN
      ** and store the values of those terms in an array of registers
      ** starting at regBase.
      */
      regBase = codeAllEqualityTerms(pParse, pLevel, &wc, notReady, 2);
      addrNxt = pLevel->addrNxt;

      /* If this loop satisfies a sort order (pOrderBy) request that 
      ** was passed to this function to implement a "SELECT min(x) ..." 
      ** query, then the caller will only allow the loop to run for
      ** a single iteration. This means that the first row returned
      ** should not have a NULL value stored in 'x'. If column 'x' is
      ** the first one after the nEq equality constraints in the index,

      if( pRangeStart ){
        int dcc = pParse->disableColCache;
        if( pRangeEnd ){
          pParse->disableColCache++;
        }
        sqlite3ExprCode(pParse, pRangeStart->pExpr->pRight, regBase+nEq);
        pParse->disableColCache = dcc;
        sqlite3VdbeAddOp2(v, OP_IsNull, regBase+nEq, addrNxt);
        nConstraint++;
      }else if( isMinQuery ){
        sqlite3VdbeAddOp2(v, OP_Null, 0, regBase+nEq);
        nConstraint++;
        startEq = 0;
        start_constraints = 1;
      }
      codeApplyAffinity(pParse, regBase, nConstraint, pIdx);
      op = aStartOp[(start_constraints<<2) + (startEq<<1) + bRev];
      assert( op!=0 );
      testcase( op==OP_Rewind );
      testcase( op==OP_Last );
      testcase( op==OP_MoveGt );
      testcase( op==OP_MoveGe );
      testcase( op==OP_MoveLe );
      testcase( op==OP_MoveLt );
      sqlite3VdbeAddOp4(v, op, iIdxCur, addrNxt, regBase, 
                        SQLITE_INT_TO_PTR(nConstraint), P4_INT32);

      /* Load the value for the inequality constraint at the end of the
      ** range (if any).
      */
      nConstraint = nEq;
      if( pRangeEnd ){
        sqlite3ExprCode(pParse, pRangeEnd->pExpr->pRight, regBase+nEq);
        sqlite3VdbeAddOp2(v, OP_IsNull, regBase+nEq, addrNxt);
        codeApplyAffinity(pParse, regBase, nEq+1, pIdx);
        nConstraint++;
      }

      /* Top of the loop body */
      pLevel->p2 = sqlite3VdbeCurrentAddr(v);

      /* Check if the index cursor is past the end of the range. */
      op = aEndOp[(pRangeEnd || nEq) * (1 + bRev)];
      testcase( op==OP_Noop );
      testcase( op==OP_IdxGE );
      testcase( op==OP_IdxLT );
      sqlite3VdbeAddOp4(v, op, iIdxCur, addrNxt, regBase,
                        SQLITE_INT_TO_PTR(nConstraint), P4_INT32);
      sqlite3VdbeChangeP5(v, endEq!=bRev);

      /* If there are inequality constraints, check that the value
      ** of the table column that the inequality contrains is not NULL.
      ** If it is, jump to the next iteration of the loop.
      */
      r1 = sqlite3GetTempReg(pParse);
      testcase( pLevel->wsFlags & WHERE_BTM_LIMIT );
      testcase( pLevel->wsFlags & WHERE_TOP_LIMIT );
      if( pLevel->wsFlags & (WHERE_BTM_LIMIT|WHERE_TOP_LIMIT) ){
        sqlite3VdbeAddOp3(v, OP_Column, iIdxCur, nEq, r1);
        sqlite3VdbeAddOp2(v, OP_IsNull, r1, addrCont);
      }

      /* Seek the table cursor, if required */
      if( !omitTable ){
        sqlite3VdbeAddOp2(v, OP_IdxRowid, iIdxCur, r1);
        sqlite3VdbeAddOp3(v, OP_MoveGe, iCur, 0, r1);  /* Deferred seek */
      }

      /* Case 4:  There is no usable index.  We must do a complete
      **          scan of the entire table.
      */
      assert( omitTable==0 );
      assert( bRev==0 );
      pLevel->op = OP_Next;
      pLevel->p1 = iCur;
      pLevel->p2 = 1 + sqlite3VdbeAddOp2(v, OP_Rewind, iCur, addrBrk);
      pLevel->p5 = SQLITE_STMTSTATUS_FULLSCAN_STEP;
    }
    notReady &= ~getMask(&maskSet, iCur);

    /* Insert code to test every subexpression that can be completely
    ** computed using the current set of tables.
    */
    k = 0;
    for(pTerm=wc.a, j=wc.nTerm; j>0; j--, pTerm++){
      Expr *pE;
      testcase( pTerm->wtFlags & TERM_VIRTUAL );
      testcase( pTerm->wtFlags & TERM_CODED );
      if( pTerm->wtFlags & (TERM_VIRTUAL|TERM_CODED) ) continue;
      if( (pTerm->prereqAll & notReady)!=0 ) continue;
      pE = pTerm->pExpr;
      assert( pE!=0 );
      if( pLevel->iLeftJoin && !ExprHasProperty(pE, EP_FromJoin) ){
        continue;
      }
      pParse->disableColCache += k;
      sqlite3ExprIfFalse(pParse, pE, addrCont, SQLITE_JUMPIFNULL);
      pParse->disableColCache -= k;
      k = 1;
      pTerm->wtFlags |= TERM_CODED;
    }

    /* For a LEFT OUTER JOIN, generate code that will record the fact that
    ** at least one row of the right table has matched the left table.  
    */
    if( pLevel->iLeftJoin ){
      pLevel->addrFirst = sqlite3VdbeCurrentAddr(v);
      sqlite3VdbeAddOp2(v, OP_Integer, 1, pLevel->iLeftJoin);
      VdbeComment((v, "record LEFT JOIN hit"));
      sqlite3ExprClearColumnCache(pParse, pLevel->iTabCur);
      sqlite3ExprClearColumnCache(pParse, pLevel->iIdxCur);
      for(pTerm=wc.a, j=0; j<wc.nTerm; j++, pTerm++){
        testcase( pTerm->wtFlags & TERM_VIRTUAL );
        testcase( pTerm->wtFlags & TERM_CODED );
        if( pTerm->wtFlags & (TERM_VIRTUAL|TERM_CODED) ) continue;
        if( (pTerm->prereqAll & notReady)!=0 ) continue;
        assert( pTerm->pExpr );
        sqlite3ExprIfFalse(pParse, pTerm->pExpr, addrCont, SQLITE_JUMPIFNULL);
        pTerm->wtFlags |= TERM_CODED;
      }
    }
  }

#ifdef SQLITE_TEST  /* For testing and debugging use only */
  /* Record in the query plan information about the current table

  sqlite3_query_plan[nQPlan] = 0;
  nQPlan = 0;
#endif /* SQLITE_TEST // Testing and debugging use only */

  /* Record the continuation address in the WhereInfo structure.  Then
  ** clean up and return.
  */
  pWInfo->iContinue = addrCont;
  whereClauseClear(&wc);
  return pWInfo;

  /* Jump here if malloc fails */
whereBeginError:
  whereClauseClear(&wc);
  whereInfoFree(db, pWInfo);

  sqlite3 *db = pParse->db;

  /* Generate loop termination code.
  */
  sqlite3ExprClearColumnCache(pParse, -1);
  for(i=pTabList->nSrc-1; i>=0; i--){
    pLevel = &pWInfo->a[i];
    sqlite3VdbeResolveLabel(v, pLevel->addrCont);
    if( pLevel->op!=OP_Noop ){
      sqlite3VdbeAddOp2(v, pLevel->op, pLevel->p1, pLevel->p2);
      sqlite3VdbeChangeP5(v, pLevel->p5);
    }
    if( pLevel->nIn ){
      struct InLoop *pIn;
      int j;
      sqlite3VdbeResolveLabel(v, pLevel->addrNxt);
      for(j=pLevel->nIn, pIn=&pLevel->aInLoop[j-1]; j>0; j--, pIn--){
        sqlite3VdbeJumpHere(v, pIn->addrInTop+1);
        sqlite3VdbeAddOp2(v, OP_Next, pIn->iCur, pIn->addrInTop);
        sqlite3VdbeJumpHere(v, pIn->addrInTop-1);
      }
      sqlite3DbFree(db, pLevel->aInLoop);
    }
    sqlite3VdbeResolveLabel(v, pLevel->addrBrk);
    if( pLevel->iLeftJoin ){
      int addr;
      addr = sqlite3VdbeAddOp1(v, OP_IfPos, pLevel->iLeftJoin);
      sqlite3VdbeAddOp1(v, OP_NullRow, pTabList->a[i].iCursor);
      if( pLevel->iIdxCur>=0 ){
        sqlite3VdbeAddOp1(v, OP_NullRow, pLevel->iIdxCur);
      }
      sqlite3VdbeAddOp2(v, OP_Goto, 0, pLevel->addrFirst);
      sqlite3VdbeJumpHere(v, addr);
    }
  }

  /* The "break" point is here, just past the end of the outer loop.
  ** Set it.
  */

      } elseif {[regexp $varpattern $line all varname]} {
        # Add the SQLITE_PRIVATE before variable declarations or
        # definitions for internal use
        if {![regexp {^sqlite3_} $varname]} {
          regsub {^extern } $line {} line
          puts $out "SQLITE_PRIVATE $line"
        } else {
          if {[regexp {const char sqlite3_version\[\];} $line]} {
            set line {const char sqlite3_version[] = SQLITE_VERSION;}
          }
          regsub {^SQLITE_EXTERN } $line {} line
          puts $out "SQLITE_API $line"
        }
      } elseif {[regexp {^(SQLITE_EXTERN )?void \(\*sqlite3IoTrace\)} $line]} {
        regsub {^SQLITE_EXTERN } $line {} line
        puts $out "SQLITE_PRIVATE $line"
      } else {