SQLite

**     COPY
**     VACUUM
**     BEGIN TRANSACTION
**     COMMIT
**     ROLLBACK
**     PRAGMA
**
** $Id: build.c,v 1.95 2002/05/24 20:31:37 drh Exp $
*/
#include "sqliteInt.h"
#include <ctype.h>

/*
** This routine is called after a single SQL statement has been
** parsed and we want to execute the VDBE code to implement 

  if( pList==0 ) return;
  for(i=0; i<pList->nId; i++){
    sqliteFree(pList->a[i].zName);
  }
  sqliteFree(pList->a);
  sqliteFree(pList);
}

/*
** Return the index in pList of the identifier named zId.  Return -1
** if not found.
*/
int sqliteIdListIndex(IdList *pList, const char *zName){
  int i;
  if( pList==0 ) return -1;
  for(i=0; i<pList->nId; i++){
    if( sqliteStrICmp(pList->a[i].zName, zName)==0 ) return i;
  }
  return -1;
}

/*
** Delete an entire SrcList including all its substructure.
*/
void sqliteSrcListDelete(SrcList *pList){
  int i;
  if( pList==0 ) return;

**    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 SELECT statements in SQLite.
**
** $Id: select.c,v 1.84 2002/05/24 20:31:37 drh Exp $
*/
#include "sqliteInt.h"

/*
** Allocate a new Select structure and return a pointer to that
** structure.
*/

      }
    }
    if( j>=sizeof(keywords)/sizeof(keywords[0]) ){
      jointype |= JT_ERROR;
      break;
    }
  }
  if(
     (jointype & (JT_INNER|JT_OUTER))==(JT_INNER|JT_OUTER) ||
     (jointype & JT_ERROR)!=0 ||
     (jointype & JT_RIGHT)==JT_RIGHT
  ){
    static Token dummy = { 0, 0 };
    char *zSp1 = " ", *zSp2 = " ";
    if( pB==0 ){ pB = &dummy; zSp1 = 0; }
    if( pC==0 ){ pC = &dummy; zSp2 = 0; }
    sqliteSetNString(&pParse->zErrMsg, "unknown or unsupported join type: ", 0,
       pA->z, pA->n, zSp1, 1, pB->z, pB->n, zSp2, 1, pC->z, pC->n, 0);
    pParse->nErr++;
    jointype = JT_INNER;
  }
  return jointype;
}

/*
** Return the index of a column in a table.  Return -1 if the column
** is not contained in the table.
*/
static int columnIndex(Table *pTab, const char *zCol){
  int i;
  for(i=0; i<pTab->nCol; i++){
    if( sqliteStrICmp(pTab->aCol[i].zName, zCol)==0 ) return i;
  }
  return -1;
}

/*
** Add a term to the WHERE expression in *ppExpr that requires the
** zCol column to be equal in the two tables pTab1 and pTab2.
*/
static void addWhereTerm(
  const char *zCol,        /* Name of the column */
  const Table *pTab1,      /* First table */
  const Table *pTab2,      /* Second table */
  Expr **ppExpr            /* Add the equality term to this expression */
){
  Token dummy;
  Expr *pE1a, *pE1b, *pE1c;
  Expr *pE2a, *pE2b, *pE2c;
  Expr *pE;

  dummy.z = zCol;
  dummy.n = strlen(zCol);
  pE1a = sqliteExpr(TK_ID, 0, 0, &dummy);
  pE2a = sqliteExpr(TK_ID, 0, 0, &dummy);
  dummy.z = pTab1->zName;
  dummy.n = strlen(dummy.z);
  pE1b = sqliteExpr(TK_ID, 0, 0, &dummy);
  dummy.z = pTab2->zName;
  dummy.n = strlen(dummy.z);
  pE2b = sqliteExpr(TK_ID, 0, 0, &dummy);
  pE1c = sqliteExpr(TK_DOT, pE1b, pE1a, 0);
  pE2c = sqliteExpr(TK_DOT, pE2b, pE2a, 0);
  pE = sqliteExpr(TK_EQ, pE1c, pE2c, 0);
  if( *ppExpr ){
    *ppExpr = sqliteExpr(TK_AND, *ppExpr, pE, 0);
  }else{
    *ppExpr = pE;
  }
}

/*
** This routine processes the join information for a SELECT statement.
** ON and USING clauses are converted into extra terms of the WHERE clause.
** NATURAL joins also create extra WHERE clause terms.
**
** This routine returns the number of errors encountered.
*/
static int sqliteProcessJoin(Parse *pParse, Select *p){
  SrcList *pSrc;
  int i, j;
  pSrc = p->pSrc;
  for(i=0; i<pSrc->nSrc-1; i++){
    struct SrcList_item *pTerm = &pSrc->a[i];
    struct SrcList_item *pOther = &pSrc->a[i+1];

    if( pTerm->pTab==0 || pOther->pTab==0 ) continue;

    /* When the NATURAL keyword is present, add WHERE clause terms for
    ** every column that the two tables have in common.
    */
    if( pTerm->jointype & JT_NATURAL ){
      Table *pTab;
      if( pTerm->pOn || pTerm->pUsing ){
        sqliteSetString(&pParse->zErrMsg, "a NATURAL join may not have "
           "an ON or USING clause", 0);
        pParse->nErr++;
        return 1;
      }
      pTab = pTerm->pTab;
      for(j=0; j<pTab->nCol; j++){
        if( columnIndex(pOther->pTab, pTab->aCol[j].zName)>=0 ){
          addWhereTerm(pTab->aCol[j].zName, pTab, pOther->pTab, &p->pWhere);
        }
      }
    }

    /* Disallow both ON and USING clauses in the same join
    */
    if( pTerm->pOn && pTerm->pUsing ){
      sqliteSetString(&pParse->zErrMsg, "cannot have both ON and USING "
        "clauses in the same join", 0);
      pParse->nErr++;
      return 1;
    }

    /* Add the ON clause to the end of the WHERE clause, connected by
    ** and AND operator.
    */
    if( pTerm->pOn ){
      if( p->pWhere==0 ){
        p->pWhere = pTerm->pOn;
      }else{
        p->pWhere = sqliteExpr(TK_AND, p->pWhere, pTerm->pOn, 0);
      }
      pTerm->pOn = 0;
    }

    /* Create extra terms on the WHERE clause for each column named
    ** in the USING clause.  Example: If the two tables to be joined are 
    ** A and B and the USING clause names X, Y, and Z, then add this
    ** to the WHERE clause:    A.X=B.X AND A.Y=B.Y AND A.Z=B.Z
    ** Report an error if any column mentioned in the USING clause is
    ** not contained in both tables to be joined.
    */
    if( pTerm->pUsing ){
      IdList *pList;
      int j;
      assert( i<pSrc->nSrc-1 );
      pList = pTerm->pUsing;
      for(j=0; j<pList->nId; j++){
        if( columnIndex(pTerm->pTab, pList->a[i].zName)<0 ||
            columnIndex(pOther->pTab, pList->a[i].zName)<0 ){
          sqliteSetString(&pParse->zErrMsg, "cannot join using column ",
            pList->a[i].zName, " - column not present in both tables", 0);
          pParse->nErr++;
          return 1;
        }
        addWhereTerm(pList->a[i].zName, pTerm->pTab, pOther->pTab, &p->pWhere);
      }
    }
  }
  return 0;
}

/*
** Delete the given Select structure and all of its substructures.
*/
void sqliteSelectDelete(Select *p){
  if( p==0 ) return;
  sqliteExprListDelete(p->pEList);

    }
  }
  pTab->iPKey = -1;
  return pTab;
}

/*
** For the given SELECT statement, do three things.
**
**    (1)  Fill in the pTabList->a[].pTab fields in the SrcList that 
**         defines the set of tables that should be scanned. 
**
**    (2)  Add terms to the WHERE clause to accomodate the NATURAL keyword
**         on joins and the ON and USING clause of joins.
**
**    (3)  Scan the list of columns in the result set (pEList) looking
**         for instances of the "*" operator or the TABLE.* operator.
**         If found, expand each "*" to be every column in every table
**         and TABLE.* to be every column in TABLE.
**
** Return 0 on success.  If there are problems, leave an error message
** in pParse and return non-zero.
*/

    if( pTabList->a[i].pTab ){
      /* This routine has run before!  No need to continue */
      return 0;
    }
    if( pTabList->a[i].zName==0 ){
      /* A sub-query in the FROM clause of a SELECT */
      assert( pTabList->a[i].pSelect!=0 );
      if( pTabList->a[i].zAlias==0 ){
        char zFakeName[60];
        sprintf(zFakeName, "sqlite_subquery_%p_",
           (void*)pTabList->a[i].pSelect);
        sqliteSetString(&pTabList->a[i].zAlias, zFakeName, 0);
      }
      pTabList->a[i].pTab = pTab = 
        sqliteResultSetOfSelect(pParse, pTabList->a[i].zAlias,
                                        pTabList->a[i].pSelect);
      if( pTab==0 ){
        return 1;
      }
      pTab->isTransient = 1;

        if( sqliteViewGetColumnNames(pParse, pTab) ){
          return 1;
        }
        pTabList->a[i].pSelect = sqliteSelectDup(pTab->pSelect);
      }
    }
  }

  /* Process NATURAL keywords, and ON and USING clauses of joins.
  */
  if( sqliteProcessJoin(pParse, p) ) return 1;

  /* For every "*" that occurs in the column list, insert the names of
  ** all columns in all tables.  And for every TABLE.* insert the names
  ** of all columns in TABLE.  The parser inserted a special expression
  ** with the TK_ALL operator for each "*" that it found in the column list.
  ** The following code just has to locate the TK_ALL expressions and expand
  ** each one to the list of all columns in all tables.

          if( pName && (zTabName==0 || zTabName[0]==0 ||
                sqliteStrNICmp(pName->z, zTabName, pName->n)!=0) ){
            continue;
          }
          tableSeen = 1;
          for(j=0; j<pTab->nCol; j++){
            Expr *pExpr, *pLeft, *pRight;
            char *zName = pTab->aCol[j].zName;

            if( i>0 && (pTabList->a[i-1].jointype & JT_NATURAL)!=0 &&
                columnIndex(pTabList->a[i-1].pTab, zName)>=0 ){
              /* In a NATURAL join, omit the join columns from the 
              ** table on the right */
              continue;
            }
            if( i>0 && sqliteIdListIndex(pTabList->a[i-1].pUsing, zName)>=0 ){
              /* In a join with a USING clause, omit columns in the
              ** using clause from the table on the right. */
              continue;
            }
            pRight = sqliteExpr(TK_ID, 0, 0, 0);
            if( pRight==0 ) break;
            pRight->token.z = zName;
            pRight->token.n = strlen(zName);
            if( zTabName ){
              pLeft = sqliteExpr(TK_ID, 0, 0, 0);
              if( pLeft==0 ) break;
              pLeft->token.z = zTabName;
              pLeft->token.n = strlen(zTabName);
              pExpr = sqliteExpr(TK_DOT, pLeft, pRight, 0);
              if( pExpr==0 ) break;

  /* Look up every table in the table list and create an appropriate
  ** columnlist in pEList if there isn't one already.  (The parser leaves
  ** a NULL in the p->pEList if the SQL said "SELECT * FROM ...")
  */
  if( fillInColumnList(pParse, p) ){
    goto select_end;
  }
  pWhere = p->pWhere;
  pEList = p->pEList;
  if( pEList==0 ) goto select_end;

  /* If writing to memory or generating a set
  ** only a single column may be output.
  */
  if( (eDest==SRT_Mem || eDest==SRT_Set) && pEList->nExpr>1 ){

/*
** 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.115 2002/05/24 20:31:37 drh Exp $
*/
#include "sqlite.h"
#include "hash.h"
#include "vdbe.h"
#include "parse.h"
#include "btree.h"
#include <stdio.h>

  int iMem;            /* Memory cell used by this level */
  Index *pIdx;         /* Index used */
  int iCur;            /* Cursor number used for this index */
  int score;           /* How well this indexed scored */
  int brk;             /* Jump here to break out of the loop */
  int cont;            /* Jump here to continue with the next loop cycle */
  int op, p1, p2;      /* Opcode used to terminate the loop */
  int iLeftJoin;       /* Memory cell used to implement LEFT OUTER JOIN */
  int top;             /* First instruction of interior of the loop */
};

/*
** The WHERE clause processing routine has two halves.  The
** first part does the start of the WHERE loop and the second
** half does the tail of the WHERE loop.  An instance of
** this structure is returned by the first half and passed

void sqliteCreateView(Parse*,Token*,Token*,Select*);
int sqliteViewGetColumnNames(Parse*,Table*);
void sqliteViewResetAll(sqlite*);
void sqliteDropTable(Parse*, Token*, int);
void sqliteDeleteTable(sqlite*, Table*);
void sqliteInsert(Parse*, Token*, ExprList*, Select*, IdList*, int);
IdList *sqliteIdListAppend(IdList*, Token*);
int sqliteIdListIndex(IdList*,const char*);
SrcList *sqliteSrcListAppend(SrcList*, Token*);
void sqliteSrcListAddAlias(SrcList*, Token*);
void sqliteIdListDelete(IdList*);
void sqliteSrcListDelete(SrcList*);
void sqliteCreateIndex(Parse*, Token*, Token*, IdList*, int, Token*, Token*);
void sqliteDropIndex(Parse*, Token*);
int sqliteSelect(Parse*, Select*, int, int, Select*, int, int*);

** in pEList have an <id> which matches an identifier in pIdList,
** then return TRUE.  If pIdList==NULL, then it is considered a
** wildcard that matches anything.  Likewise if pEList==NULL then
** it matches anything so always return true.  Return false only
** if there is no match.
*/
static int checkColumnOverLap(IdList *pIdList, ExprList *pEList){
  int e;
  if( !pIdList || !pEList ) return 1;



  for(e=0; e<pEList->nExpr; e++){
    if( sqliteIdListIndex(pIdList, pEList->a[e].zName)>=0 ) return 1;

  }



  return 0; 
}

/* A global variable that is TRUE if we should always set up temp tables for
 * for triggers, even if there are no triggers to code. This is used to test 
 * how much overhead the triggers algorithm is causing.
 *

** 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.
**
** $Id: vdbe.c,v 1.148 2002/05/24 20:31:37 drh Exp $
*/
#include "sqliteInt.h"
#include <ctype.h>

/*
** The following global variable is incremented every time a cursor
** moves, either by the OP_MoveTo or the OP_Next opcode.  The test

*/
case OP_Next: {
  int i = pOp->p1;
  BtCursor *pCrsr;

  if( VERIFY( i>=0 && i<p->nCursor && ) (pCrsr = p->aCsr[i].pCursor)!=0 ){
    int res;
    if( p->aCsr[i].nullRow ){
      res = 1;
    }else{
      rc = sqliteBtreeNext(pCrsr, &res);
      p->aCsr[i].nullRow = res;
    }
    if( res==0 ){
      pc = pOp->p2 - 1;
      sqlite_search_count++;
    }
    p->aCsr[i].recnoIsValid = 0;
  }
  break;

**    May you share freely, never taking more than you give.
**
*************************************************************************
** This module contains C code that generates VDBE code used to process
** the WHERE clause of SQL statements.  Also found here are subroutines
** to generate VDBE code to evaluate expressions.
**
** $Id: where.c,v 1.47 2002/05/24 20:31:38 drh Exp $
*/
#include "sqliteInt.h"

/*
** The query generator uses an array of instances of this structure to
** help it analyze the subexpressions of the WHERE clause.  Each WHERE
** clause subexpression is separated from the others by an AND operator.

  */
  loopMask = 0;
  for(i=0; i<pTabList->nSrc; i++){
    int j, k;
    int idx = aOrder[i];
    Index *pIdx;
    WhereLevel *pLevel = &pWInfo->a[i];

    /* If this is the right table of a LEFT OUTER JOIN, allocate and
    ** initialize a memory cell that record if this table matches any
    ** row of the left table in the join.
    */
    if( i>0 && (pTabList->a[i-1].jointype & JT_LEFT)!=0 ){
      if( !pParse->nMem ) pParse->nMem++;
      pLevel->iLeftJoin = pParse->nMem++;
      sqliteVdbeAddOp(v, OP_String, 0, 0);
      sqliteVdbeAddOp(v, OP_MemStore, pLevel->iLeftJoin, 1);
    }

    pIdx = pLevel->pIdx;
    if( i<ARRAYSIZE(iDirectEq) && iDirectEq[i]>=0 ){
      /* Case 1:  We can directly reference a single row using an
      **          equality comparison against the ROWID field.
      */
      k = iDirectEq[i];

        haveKey = 0;
        sqliteVdbeAddOp(v, OP_MoveTo, base+idx, 0);
      }
      sqliteExprIfFalse(pParse, aExpr[j].p, cont);
      aExpr[j].p = 0;
    }
    brk = cont;

    /* 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->top = sqliteVdbeCurrentAddr(v);
      sqliteVdbeAddOp(v, OP_Integer, 1, 0);
      sqliteVdbeAddOp(v, OP_MemStore, pLevel->iLeftJoin, 1);
    }
  }
  pWInfo->iContinue = cont;
  if( pushKey && !haveKey ){
    sqliteVdbeAddOp(v, OP_Recno, base, 0);
  }
  sqliteFree(aOrder);
  return pWInfo;

  for(i=pTabList->nSrc-1; i>=0; i--){
    pLevel = &pWInfo->a[i];
    sqliteVdbeResolveLabel(v, pLevel->cont);
    if( pLevel->op!=OP_Noop ){
      sqliteVdbeAddOp(v, pLevel->op, pLevel->p1, pLevel->p2);
    }
    sqliteVdbeResolveLabel(v, pLevel->brk);
    if( pLevel->iLeftJoin ){
      int addr;
      addr = sqliteVdbeAddOp(v, OP_MemLoad, pLevel->iLeftJoin, 0);
      sqliteVdbeAddOp(v, OP_NotNull, 0, addr+4);
      sqliteVdbeAddOp(v, OP_NullRow, base+i, 0);
      sqliteVdbeAddOp(v, OP_Goto, 0, pLevel->top);
    }
  }
  sqliteVdbeResolveLabel(v, pWInfo->iBreak);
  for(i=0; i<pTabList->nSrc; i++){
    if( pTabList->a[i].pTab->isTransient ) continue;
    pLevel = &pWInfo->a[i];
    sqliteVdbeAddOp(v, OP_Close, base+i, 0);
    if( pLevel->pIdx!=0 ){

# 2002 May 24
#
# 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 implements regression tests for SQLite library.
#
# This file implements tests for joins, including outer joins.
#
# $Id: join.test,v 1.1 2002/05/24 20:31:38 drh Exp $

set testdir [file dirname $argv0]
source $testdir/tester.tcl

do_test join-1.1 {
  execsql {
    CREATE TABLE t1(a,b,c);
    INSERT INTO t1 VALUES(1,2,3);
    INSERT INTO t1 VALUES(2,3,4);
    INSERT INTO t1 VALUES(3,4,5);
    SELECT * FROM t1;
  }  
} {1 2 3 2 3 4 3 4 5}
do_test join-1.2 {
  execsql {
    CREATE TABLE t2(b,c,d);
    INSERT INTO t2 VALUES(1,2,3);
    INSERT INTO t2 VALUES(2,3,4);
    INSERT INTO t2 VALUES(3,4,5);
    SELECT * FROM t2;
  }  
} {1 2 3 2 3 4 3 4 5}

do_test join-1.3 {
  execsql2 {
    SELECT * FROM t1 NATURAL JOIN t2;
  }
} {t1.a 1 t1.b 2 t1.c 3 t2.d 4 t1.a 2 t1.b 3 t1.c 4 t2.d 5}
do_test join-1.4 {
  execsql2 {
    SELECT * FROM t1 INNER JOIN t2 USING(b,c);
  }
} {t1.a 1 t1.b 2 t1.c 3 t2.d 4 t1.a 2 t1.b 3 t1.c 4 t2.d 5}
do_test join-1.5 {
  execsql2 {
    SELECT * FROM t1 INNER JOIN t2 USING(b);
  }
} {t1.a 1 t1.b 2 t1.c 3 t2.c 3 t2.d 4 t1.a 2 t1.b 3 t1.c 4 t2.c 4 t2.d 5}
do_test join-1.6 {
  execsql2 {
    SELECT * FROM t1 INNER JOIN t2 USING(c);
  }
} {t1.a 1 t1.b 2 t1.c 3 t2.b 2 t2.d 4 t1.a 2 t1.b 3 t1.c 4 t2.b 3 t2.d 5}
do_test join-1.7 {
  execsql2 {
    SELECT * FROM t1 INNER JOIN t2 USING(c,b);
  }
} {t1.a 1 t1.b 2 t1.c 3 t2.d 4 t1.a 2 t1.b 3 t1.c 4 t2.d 5}

do_test join-2.1 {
  execsql {
    SELECT * FROM t1 NATURAL LEFT JOIN t2;
  }
} {1 2 3 4 2 3 4 5 3 4 5 {}}

finish_test

# 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 implements regression tests for SQLite library.  The
# focus of this file is testing the SELECT statement.
#
# $Id: select1.test,v 1.26 2002/05/24 20:31:38 drh Exp $

set testdir [file dirname $argv0]
source $testdir/tester.tcl

# Try to select on a non-existant table.
#
do_test select1-1.1 {

do_test select1-11.13 {
  execsql2 {
    SELECT t3.* FROM (SELECT max(a), max(b) FROM t4), t3
  }
} {t3.a 1 t3.b 2}
do_test select1-11.14 {
  execsql2 {
    SELECT * FROM t3, (SELECT max(a), max(b) FROM t4) AS 'tx'
  }
} {t3.a 1 t3.b 2 tx.max(a) 3 tx.max(b) 4}
do_test select1-11.15 {
  execsql2 {
    SELECT y.*, t3.* FROM t3, (SELECT max(a), max(b) FROM t4) AS y
  }
} {y.max(a) 3 y.max(b) 4 t3.a 1 t3.b 2}

# Tests of SELECT statements without a FROM clause.