**
*************************************************************************
** This file contains SQLite's grammar for SQL.  Process this file
** using the lemon parser generator to generate C code that runs
** the parser.  Lemon will also generate a header file containing
** numeric codes for all of the tokens.
**
** @(#) $Id: parse.y,v 1.68 2002/05/24 02:04:33 drh Exp $
*/
%token_prefix TK_
%token_type {Token}
%default_type {Token}
%extra_argument {Parse *pParse}
%syntax_error {
  sqliteSetString(&pParse->zErrMsg,"syntax error",0);
................................................................................
id(A) ::= END(X).        {A = X;}
id(A) ::= EXPLAIN(X).    {A = X;}
id(A) ::= FAIL(X).       {A = X;}
id(A) ::= FOR(X).        {A = X;}
id(A) ::= ID(X).         {A = X;}
id(A) ::= IGNORE(X).     {A = X;}
id(A) ::= INSTEAD(X).    {A = X;}

id(A) ::= KEY(X).        {A = X;}
id(A) ::= OF(X).         {A = X;}
id(A) ::= OFFSET(X).     {A = X;}
id(A) ::= PRAGMA(X).     {A = X;}
id(A) ::= REPLACE(X).    {A = X;}
id(A) ::= ROW(X).        {A = X;}
id(A) ::= STATEMENT(X).  {A = X;}
................................................................................
//
%type selcollist {ExprList*}
%destructor selcollist {sqliteExprListDelete($$);}
%type sclp {ExprList*}
%destructor sclp {sqliteExprListDelete($$);}
sclp(A) ::= selcollist(X) COMMA.             {A = X;}
sclp(A) ::= .                                {A = 0;}
selcollist(A) ::= sclp(P) expr(X).           {A = sqliteExprListAppend(P,X,0);}
selcollist(A) ::= sclp(P) expr(X) as ids(Y). {A = sqliteExprListAppend(P,X,&Y);}

selcollist(A) ::= sclp(P) STAR. {
  A = sqliteExprListAppend(P, sqliteExpr(TK_ALL, 0, 0, 0), 0);
}
selcollist(A) ::= sclp(P) ids(X) DOT STAR. {
  Expr *pRight = sqliteExpr(TK_ALL, 0, 0, 0);
  Expr *pLeft = sqliteExpr(TK_ID, 0, 0, &X);
  A = sqliteExprListAppend(P, sqliteExpr(TK_DOT, pLeft, pRight, 0), 0);
}
as ::= .

as ::= AS.







%type seltablist {SrcList*}
%destructor seltablist {sqliteSrcListDelete($$);}
%type stl_prefix {SrcList*}
%destructor stl_prefix {sqliteSrcListDelete($$);}
%type from {SrcList*}
%destructor from {sqliteSrcListDelete($$);}



from(A) ::= .                                 {A = sqliteMalloc(sizeof(*A));}
from(A) ::= FROM seltablist(X).               {A = X;}




stl_prefix(A) ::= seltablist(X) COMMA.        {A = X;}



stl_prefix(A) ::= .                           {A = 0;}
seltablist(A) ::= stl_prefix(X) ids(Y).       {A = sqliteSrcListAppend(X,&Y);}
seltablist(A) ::= stl_prefix(X) ids(Y) as ids(Z). {
  A = sqliteSrcListAppend(X,&Y);
  sqliteSrcListAddAlias(A,&Z);



}





seltablist(A) ::= stl_prefix(X) LP select(S) RP. {
  A = sqliteSrcListAppend(X,0);
  A->a[A->nSrc-1].pSelect = S;
  if( S->pOrderBy ){
    sqliteExprListDelete(S->pOrderBy);
    S->pOrderBy = 0;
  }




}
seltablist(A) ::= stl_prefix(X) LP select(S) RP as ids(Z). {
  A = sqliteSrcListAppend(X,0);
  A->a[A->nSrc-1].pSelect = S;
  if( S->pOrderBy ){
    sqliteExprListDelete(S->pOrderBy);
    S->pOrderBy = 0;

  }
  sqliteSrcListAddAlias(A,&Z);
}




















%type orderby_opt {ExprList*}
%destructor orderby_opt {sqliteExprListDelete($$);}
%type sortlist {ExprList*}
%destructor sortlist {sqliteExprListDelete($$);}
%type sortitem {Expr*}
%destructor sortitem {sqliteExprDelete($$);}

**
*************************************************************************
** This file contains SQLite's grammar for SQL.  Process this file
** using the lemon parser generator to generate C code that runs
** the parser.  Lemon will also generate a header file containing
** numeric codes for all of the tokens.
**
** @(#) $Id: parse.y,v 1.69 2002/05/24 16:14:15 drh Exp $
*/
%token_prefix TK_
%token_type {Token}
%default_type {Token}
%extra_argument {Parse *pParse}
%syntax_error {
  sqliteSetString(&pParse->zErrMsg,"syntax error",0);
................................................................................
id(A) ::= END(X).        {A = X;}
id(A) ::= EXPLAIN(X).    {A = X;}
id(A) ::= FAIL(X).       {A = X;}
id(A) ::= FOR(X).        {A = X;}
id(A) ::= ID(X).         {A = X;}
id(A) ::= IGNORE(X).     {A = X;}
id(A) ::= INSTEAD(X).    {A = X;}
id(A) ::= JOIN(X).       {A = X;}
id(A) ::= KEY(X).        {A = X;}
id(A) ::= OF(X).         {A = X;}
id(A) ::= OFFSET(X).     {A = X;}
id(A) ::= PRAGMA(X).     {A = X;}
id(A) ::= REPLACE(X).    {A = X;}
id(A) ::= ROW(X).        {A = X;}
id(A) ::= STATEMENT(X).  {A = X;}
................................................................................
//
%type selcollist {ExprList*}
%destructor selcollist {sqliteExprListDelete($$);}
%type sclp {ExprList*}
%destructor sclp {sqliteExprListDelete($$);}
sclp(A) ::= selcollist(X) COMMA.             {A = X;}
sclp(A) ::= .                                {A = 0;}
selcollist(A) ::= sclp(P) expr(X) as(Y).     {
   A = sqliteExprListAppend(P,X,Y.n?&Y:0);
}
selcollist(A) ::= sclp(P) STAR. {
  A = sqliteExprListAppend(P, sqliteExpr(TK_ALL, 0, 0, 0), 0);
}
selcollist(A) ::= sclp(P) ids(X) DOT STAR. {
  Expr *pRight = sqliteExpr(TK_ALL, 0, 0, 0);
  Expr *pLeft = sqliteExpr(TK_ID, 0, 0, &X);
  A = sqliteExprListAppend(P, sqliteExpr(TK_DOT, pLeft, pRight, 0), 0);
}


// An option "AS <id>" phrase that can follow one of the expressions that
// define the result set, or one of the tables in the FROM clause.
//
%type as {Token}
as(X) ::= AS ids(Y).    { X = Y; }
as(X) ::= .             { X.n = 0; }


%type seltablist {SrcList*}
%destructor seltablist {sqliteSrcListDelete($$);}
%type stl_prefix {SrcList*}
%destructor stl_prefix {sqliteSrcListDelete($$);}
%type from {SrcList*}
%destructor from {sqliteSrcListDelete($$);}

// A complete FROM clause.
//
from(A) ::= .                                 {A = sqliteMalloc(sizeof(*A));}
from(A) ::= FROM seltablist(X).               {A = X;}

// "seltablist" is a "Select Table List" - the content of the FROM clause
// in a SELECT statement.  "stl_prefix" is a prefix of this list.
//
stl_prefix(A) ::= seltablist(X) joinop(Y).    {
   A = X;
   if( A && A->nSrc>0 ) A->a[A->nSrc-1].jointype = Y;
}
stl_prefix(A) ::= .                           {A = 0;}

seltablist(A) ::= stl_prefix(X) ids(Y) as(Z) on_opt(N) using_opt(U). {
  A = sqliteSrcListAppend(X,&Y);
  if( Z.n ) sqliteSrcListAddAlias(A,&Z);
  if( N ){
    if( A && A->nSrc>1 ){ A->a[A->nSrc-2].pOn = N; }
    else { sqliteExprDelete(N); }
  }
  if( U ){
    if( A && A->nSrc>1 ){ A->a[A->nSrc-2].pUsing = U; }
    else { sqliteIdListDelete(U); }
  }
}
seltablist(A) ::= stl_prefix(X) LP select(S) RP as(Z) on_opt(N) using_opt(U). {
  A = sqliteSrcListAppend(X,0);
  A->a[A->nSrc-1].pSelect = S;
  if( S->pOrderBy ){
    sqliteExprListDelete(S->pOrderBy);
    S->pOrderBy = 0;
  }
  if( Z.n ) sqliteSrcListAddAlias(A,&Z);
  if( N ){
    if( A && A->nSrc>1 ){ A->a[A->nSrc-2].pOn = N; }
    else { sqliteExprDelete(N); }
  }




  if( U ){
    if( A && A->nSrc>1 ){ A->a[A->nSrc-2].pUsing = U; }
    else { sqliteIdListDelete(U); }
  }

}

%type joinop {int}
%type joinop2 {int}
joinop(X) ::= COMMA.                   { X = JT_INNER; }
joinop(X) ::= JOIN.                    { X = JT_INNER; }
joinop(X) ::= ID(A) JOIN.              { X = sqliteJoinType(pParse,&A,0,0); }
joinop(X) ::= ID(A) ID(B) JOIN.        { X = sqliteJoinType(pParse,&A,&B,0); }
joinop(X) ::= ID(A) ID(B) ID(C) JOIN.  { X = sqliteJoinType(pParse,&A,&B,&C); }

%type on_opt {Expr*}
%destructor on_opt {sqliteExprDelete($$);}
on_opt(N) ::= ON expr(E).   {N = E;}
on_opt(N) ::= .             {N = 0;}

%type using_opt {IdList*}
%destructor using_opt {sqliteIdListDelete($$);}
using_opt(U) ::= USING LP idxlist(L) RP.  {U = L;}
using_opt(U) ::= .                        {U = 0;}


%type orderby_opt {ExprList*}
%destructor orderby_opt {sqliteExprListDelete($$);}
%type sortlist {ExprList*}
%destructor sortlist {sqliteExprListDelete($$);}
%type sortitem {Expr*}
%destructor sortitem {sqliteExprDelete($$);}

**    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.82 2002/05/24 02:04:33 drh Exp $
*/
#include "sqliteInt.h"

/*
** Allocate a new Select structure and return a pointer to that
** structure.
*/
................................................................................
    pNew->isDistinct = isDistinct;
    pNew->op = TK_SELECT;
    pNew->nLimit = nLimit;
    pNew->nOffset = nOffset;
  }
  return pNew;
}

































































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

**    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.83 2002/05/24 16:14:15 drh Exp $
*/
#include "sqliteInt.h"

/*
** Allocate a new Select structure and return a pointer to that
** structure.
*/
................................................................................
    pNew->isDistinct = isDistinct;
    pNew->op = TK_SELECT;
    pNew->nLimit = nLimit;
    pNew->nOffset = nOffset;
  }
  return pNew;
}

/*
** Given 1 to 3 identifiers preceeding the JOIN keyword, determine the
** type of join.  Return an integer constant that expresses that type
** in terms of the following bit values:
**
**     JT_INNER
**     JT_OUTER
**     JT_NATURAL
**     JT_LEFT
**     JT_RIGHT
**
** A full outer join is the combination of JT_LEFT and JT_RIGHT.
**
** If an illegal or unsupported join type is seen, then still return
** a join type, but put an error in the pParse structure.
*/
int sqliteJoinType(Parse *pParse, Token *pA, Token *pB, Token *pC){
  int jointype = 0;
  Token *apAll[3];
  Token *p;
  static struct {
    const char *zKeyword;
    int nChar;
    int code;
  } keywords[] = {
    { "natural", 7, JT_NATURAL },
    { "left",    4, JT_LEFT },
    { "right",   5, JT_RIGHT },
    { "full",    4, JT_FULL },
    { "outer",   5, JT_OUTER },
    { "inner",   5, JT_INNER },
    { "cross",   5, JT_INNER },
  };
  int i, j;
  apAll[0] = pA;
  apAll[1] = pB;
  apAll[2] = pC;
  for(i=0; apAll[i]; i++){
    p = apAll[i];
    for(j=0; j<sizeof(keywords)/sizeof(keywords[0]); j++){
      if( p->n==keywords[j].nChar 
          && sqliteStrNICmp(p->z, keywords[j].zKeyword, p->n)==0 ){
        jointype |= keywords[j].code;
        break;
      }
    }
    if( j>=sizeof(keywords)/sizeof(keywords[0]) ){
      jointype |= JT_ERROR;
      break;
    }
  }
  if( (jointype & ~JT_INNER)!=0 ){
    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;
}

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

**    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.113 2002/05/24 02:04:33 drh Exp $
*/
#include "sqlite.h"
#include "hash.h"
#include "vdbe.h"
#include "parse.h"
#include "btree.h"
#include <stdio.h>
................................................................................
    Select *pSelect;  /* A SELECT statement used in place of a table name */
    int jointype;     /* Type of join between this table and the next */
    Expr *pOn;        /* The ON clause of a join */
    IdList *pUsing;   /* The USING clause of a join */
  } *a;            /* One entry for each identifier on the list */
};












/*
** For each nested loop in a WHERE clause implementation, the WhereInfo
** structure contains a single instance of this structure.  This structure
** is intended to be private the the where.c module and should not be
** access or modified by other modules.
*/
struct WhereLevel {
................................................................................
int sqliteCodeRowTrigger(Parse*, int, ExprList*, int, Table *, int, int, int);
void sqliteViewTriggers(Parse*, Table*, Expr*, int, ExprList*);
TriggerStep *sqliteTriggerSelectStep(Select*);
TriggerStep *sqliteTriggerInsertStep(Token*, IdList*, ExprList*, Select*, int);
TriggerStep *sqliteTriggerUpdateStep(Token*, ExprList*, Expr*, int);
TriggerStep *sqliteTriggerDeleteStep(Token*, Expr*);
void sqliteDeleteTrigger(Trigger*);

**    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.114 2002/05/24 16:14:15 drh Exp $
*/
#include "sqlite.h"
#include "hash.h"
#include "vdbe.h"
#include "parse.h"
#include "btree.h"
#include <stdio.h>
................................................................................
    Select *pSelect;  /* A SELECT statement used in place of a table name */
    int jointype;     /* Type of join between this table and the next */
    Expr *pOn;        /* The ON clause of a join */
    IdList *pUsing;   /* The USING clause of a join */
  } *a;            /* One entry for each identifier on the list */
};

/*
** Permitted values of the SrcList.a.jointype field
*/
#define JT_INNER     0x0001    /* Any kind of inner or cross join */
#define JT_NATURAL   0x0002    /* True for a "natural" join */
#define JT_LEFT      0x0014    /* Left outer join */
#define JT_RIGHT     0x0018    /* Right outer join */
#define JT_FULL      0x001a    /* Combination of left and right outer join */
#define JT_OUTER     0x0010    /* The "OUTER" keyword is present */
#define JT_ERROR     0x0020    /* unknown or unsupported join type */

/*
** For each nested loop in a WHERE clause implementation, the WhereInfo
** structure contains a single instance of this structure.  This structure
** is intended to be private the the where.c module and should not be
** access or modified by other modules.
*/
struct WhereLevel {
................................................................................
int sqliteCodeRowTrigger(Parse*, int, ExprList*, int, Table *, int, int, int);
void sqliteViewTriggers(Parse*, Table*, Expr*, int, ExprList*);
TriggerStep *sqliteTriggerSelectStep(Select*);
TriggerStep *sqliteTriggerInsertStep(Token*, IdList*, ExprList*, Select*, int);
TriggerStep *sqliteTriggerUpdateStep(Token*, ExprList*, Expr*, int);
TriggerStep *sqliteTriggerDeleteStep(Token*, Expr*);
void sqliteDeleteTrigger(Trigger*);
int sqliteJoinType(Parse*, Token*, Token*, Token*);

*************************************************************************
** An tokenizer for SQL
**
** This file contains C code that splits an SQL input string up into
** individual tokens and sends those tokens one-by-one over to the
** parser for analysis.
**
** $Id: tokenize.c,v 1.42 2002/05/23 00:30:31 drh Exp $
*/
#include "sqliteInt.h"
#include "os.h"
#include <ctype.h>
#include <stdlib.h>

/*
................................................................................
  { "INDEX",             0, TK_INDEX,            0 },
  { "INSERT",            0, TK_INSERT,           0 },
  { "INSTEAD",           0, TK_INSTEAD,          0 },
  { "INTERSECT",         0, TK_INTERSECT,        0 },
  { "INTO",              0, TK_INTO,             0 },
  { "IS",                0, TK_IS,               0 },
  { "ISNULL",            0, TK_ISNULL,           0 },

  { "KEY",               0, TK_KEY,              0 },
  { "LIKE",              0, TK_LIKE,             0 },
  { "LIMIT",             0, TK_LIMIT,            0 },
  { "NOT",               0, TK_NOT,              0 },
  { "NOTNULL",           0, TK_NOTNULL,          0 },
  { "NULL",              0, TK_NULL,             0 },
  { "OF",                0, TK_OF,               0 },

*************************************************************************
** An tokenizer for SQL
**
** This file contains C code that splits an SQL input string up into
** individual tokens and sends those tokens one-by-one over to the
** parser for analysis.
**
** $Id: tokenize.c,v 1.43 2002/05/24 16:14:15 drh Exp $
*/
#include "sqliteInt.h"
#include "os.h"
#include <ctype.h>
#include <stdlib.h>

/*
................................................................................
  { "INDEX",             0, TK_INDEX,            0 },
  { "INSERT",            0, TK_INSERT,           0 },
  { "INSTEAD",           0, TK_INSTEAD,          0 },
  { "INTERSECT",         0, TK_INTERSECT,        0 },
  { "INTO",              0, TK_INTO,             0 },
  { "IS",                0, TK_IS,               0 },
  { "ISNULL",            0, TK_ISNULL,           0 },
  { "JOIN",              0, TK_JOIN,             0 },
  { "KEY",               0, TK_KEY,              0 },
  { "LIKE",              0, TK_LIKE,             0 },
  { "LIMIT",             0, TK_LIMIT,            0 },
  { "NOT",               0, TK_NOT,              0 },
  { "NOTNULL",           0, TK_NOTNULL,          0 },
  { "NULL",              0, TK_NULL,             0 },
  { "OF",                0, TK_OF,               0 },

#    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 LIMIT ... OFFSET ... clause
#  of SELECT statements.
#
# $Id: limit.test,v 1.1 2001/11/06 14:10:42 drh Exp $

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

# Build some test data
#
set fd [open data1.txt w]
................................................................................
do_test limit-1.4 {
  execsql {SELECT x FROM t1 ORDER BY x LIMIT 50 OFFSET 30}
} {30 31}
do_test limit-1.5 {
  execsql {SELECT x FROM t1 ORDER BY x LIMIT 50 OFFSET 50}
} {}
do_test limit-1.6 {
  execsql {SELECT * FROM t1 a, t1 b ORDER BY a.x, b.x LIMIT 5}
} {0 5 0 5 0 5 1 5 0 5 2 5 0 5 3 5 0 5 4 5}
do_test limit-1.7 {
  execsql {SELECT * FROM t1 a, t1 b ORDER BY a.x, b.x LIMIT 5 OFFSET 32}
} {1 5 0 5 1 5 1 5 1 5 2 5 1 5 3 5 1 5 4 5}


finish_test

#    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 LIMIT ... OFFSET ... clause
#  of SELECT statements.
#
# $Id: limit.test,v 1.2 2002/05/24 16:14:16 drh Exp $

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

# Build some test data
#
set fd [open data1.txt w]
................................................................................
do_test limit-1.4 {
  execsql {SELECT x FROM t1 ORDER BY x LIMIT 50 OFFSET 30}
} {30 31}
do_test limit-1.5 {
  execsql {SELECT x FROM t1 ORDER BY x LIMIT 50 OFFSET 50}
} {}
do_test limit-1.6 {
  execsql {SELECT * FROM t1 AS a, t1 AS b ORDER BY a.x, b.x LIMIT 5}
} {0 5 0 5 0 5 1 5 0 5 2 5 0 5 3 5 0 5 4 5}
do_test limit-1.7 {
  execsql {SELECT * FROM t1 AS a, t1 AS b ORDER BY a.x, b.x LIMIT 5 OFFSET 32}
} {1 5 0 5 1 5 1 5 1 5 2 5 1 5 3 5 1 5 4 5}


finish_test

#    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 UNION, INTERSECT and EXCEPT operators
# in SELECT statements.
#
# $Id: select4.test,v 1.5 2002/04/23 17:10:19 drh Exp $

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

# Build some test data
#
set fd [open data1.txt w]
................................................................................
    SELECT n FROM t1 WHERE log=3
    ORDER BY xyzzy;
  }} msg]
  lappend v $msg
} {0 {0 1 2 3 4 5 5 6 7 8}}
do_test select4-5.2b {
  set v [catch {execsql {
    SELECT DISTINCT log xyzzy FROM t1
    UNION ALL
    SELECT n FROM t1 WHERE log=3
    ORDER BY 'xyzzy';
  }} msg]
  lappend v $msg
} {0 {0 1 2 3 4 5 5 6 7 8}}
do_test select4-5.2c {

#    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 UNION, INTERSECT and EXCEPT operators
# in SELECT statements.
#
# $Id: select4.test,v 1.6 2002/05/24 16:14:16 drh Exp $

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

# Build some test data
#
set fd [open data1.txt w]
................................................................................
    SELECT n FROM t1 WHERE log=3
    ORDER BY xyzzy;
  }} msg]
  lappend v $msg
} {0 {0 1 2 3 4 5 5 6 7 8}}
do_test select4-5.2b {
  set v [catch {execsql {
    SELECT DISTINCT log AS xyzzy FROM t1
    UNION ALL
    SELECT n FROM t1 WHERE log=3
    ORDER BY 'xyzzy';
  }} msg]
  lappend v $msg
} {0 {0 1 2 3 4 5 5 6 7 8}}
do_test select4-5.2c {