/*

** 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 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.204 2006/06/16 08:01:04 danielk1977 Exp $

*/

// All token codes are small integers with #defines that begin with "TK_"

%token_prefix TK_

// The type of the data attached to each token is Token.  This is also the

// default type for non-terminals.

//

%token_type {Token}

%default_type {Token}

// The generated parser function takes a 4th argument as follows:

%extra_argument {Parse *pParse}

// This code runs whenever there is a syntax error

//

%syntax_error {

  if( !pParse->parseError ){

    if( TOKEN.z[0] ){

      sqlite3ErrorMsg(pParse, "near \"%T\": syntax error", &TOKEN);

    }else{

      sqlite3ErrorMsg(pParse, "incomplete SQL statement");

    }

    pParse->parseError = 1;

  }

}

%stack_overflow {

  sqlite3ErrorMsg(pParse, "parser stack overflow");

  pParse->parseError = 1;

}

// The name of the generated procedure that implements the parser

// is as follows:

%name sqlite3Parser

// The following text is included near the beginning of the C source

// code file that implements the parser.

//

%include {

#include "sqliteInt.h"

#include "parse.h"

/*

** An instance of this structure holds information about the

** LIMIT clause of a SELECT statement.

*/

struct LimitVal {

  Expr *pLimit;    /* The LIMIT expression.  NULL if there is no limit */

  Expr *pOffset;   /* The OFFSET expression.  NULL if there is none */

};

/*

** An instance of this structure is used to store the LIKE,

** GLOB, NOT LIKE, and NOT GLOB operators.

*/

struct LikeOp {

  Token eOperator;  /* "like" or "glob" or "regexp" */

  int not;         /* True if the NOT keyword is present */

};

/*

** An instance of the following structure describes the event of a

** TRIGGER.  "a" is the event type, one of TK_UPDATE, TK_INSERT,

** TK_DELETE, or TK_INSTEAD.  If the event is of the form

**

**      UPDATE ON (a,b,c)

**

** Then the "b" IdList records the list "a,b,c".

*/

struct TrigEvent { int a; IdList * b; };

/*

** An instance of this structure holds the ATTACH key and the key type.

*/

struct AttachKey { int type;  Token key; };

} // end %include

// Input is a single SQL command

input ::= cmdlist.

cmdlist ::= cmdlist ecmd.

cmdlist ::= ecmd.

cmdx ::= cmd.           { sqlite3FinishCoding(pParse); }

ecmd ::= SEMI.

ecmd ::= explain cmdx SEMI.

explain ::= .           { sqlite3BeginParse(pParse, 0); }

%ifndef SQLITE_OMIT_EXPLAIN

explain ::= EXPLAIN.              { sqlite3BeginParse(pParse, 1); }

explain ::= EXPLAIN QUERY PLAN.   { sqlite3BeginParse(pParse, 2); }

%endif

///////////////////// Begin and end transactions. ////////////////////////////

//

cmd ::= BEGIN transtype(Y) trans_opt.  {sqlite3BeginTransaction(pParse, Y);}

trans_opt ::= .

trans_opt ::= TRANSACTION.

trans_opt ::= TRANSACTION nm.

%type transtype {int}

transtype(A) ::= .             {A = TK_DEFERRED;}

transtype(A) ::= DEFERRED(X).  {A = @X;}

transtype(A) ::= IMMEDIATE(X). {A = @X;}

transtype(A) ::= EXCLUSIVE(X). {A = @X;}

cmd ::= COMMIT trans_opt.      {sqlite3CommitTransaction(pParse);}

cmd ::= END trans_opt.         {sqlite3CommitTransaction(pParse);}

cmd ::= ROLLBACK trans_opt.    {sqlite3RollbackTransaction(pParse);}

///////////////////// The CREATE TABLE statement ////////////////////////////

//

cmd ::= create_table create_table_args.

create_table ::= CREATE temp(T) TABLE ifnotexists(E) nm(Y) dbnm(Z). {

   sqlite3StartTable(pParse,&Y,&Z,T,0,0,E);

}

%type ifnotexists {int}

ifnotexists(A) ::= .              {A = 0;}

ifnotexists(A) ::= IF NOT EXISTS. {A = 1;}

%type temp {int}

%ifndef SQLITE_OMIT_TEMPDB

temp(A) ::= TEMP.  {A = 1;}

%endif

temp(A) ::= .      {A = 0;}

create_table_args ::= LP columnlist conslist_opt(X) RP(Y). {

  sqlite3EndTable(pParse,&X,&Y,0);

}

create_table_args ::= AS select(S). {

  sqlite3EndTable(pParse,0,0,S);

  sqlite3SelectDelete(S);

}

columnlist ::= columnlist COMMA column.

columnlist ::= column.

// A "column" is a complete description of a single column in a

// CREATE TABLE statement.  This includes the column name, its

// datatype, and other keywords such as PRIMARY KEY, UNIQUE, REFERENCES,

// NOT NULL and so forth.

//

column(A) ::= columnid(X) type carglist. {

  A.z = X.z;

  A.n = (pParse->sLastToken.z-X.z) + pParse->sLastToken.n;

}

columnid(A) ::= nm(X). {

  sqlite3AddColumn(pParse,&X);

  A = X;

}

// An IDENTIFIER can be a generic identifier, or one of several

// keywords.  Any non-standard keyword can also be an identifier.

//

%type id {Token}

id(A) ::= ID(X).         {A = X;}

// The following directive causes tokens ABORT, AFTER, ASC, etc. to

// fallback to ID if they will not parse as their original value.

// This obviates the need for the "id" nonterminal.

//

%fallback ID

  ABORT AFTER ANALYZE ASC ATTACH BEFORE BEGIN CASCADE CAST CONFLICT

  DATABASE DEFERRED DESC DETACH EACH END EXCLUSIVE EXPLAIN FAIL FOR

  IGNORE IMMEDIATE INITIALLY INSTEAD LIKE_KW MATCH PLAN QUERY KEY

  OF OFFSET PRAGMA RAISE REPLACE RESTRICT ROW STATEMENT

  TEMP TRIGGER VACUUM VIEW VIRTUAL

%ifdef SQLITE_OMIT_COMPOUND_SELECT

  EXCEPT INTERSECT UNION

%endif

  REINDEX RENAME CTIME_KW IF

  .

%wildcard ANY.

// Define operator precedence early so that this is the first occurance

// of the operator tokens in the grammer.  Keeping the operators together

// causes them to be assigned integer values that are close together,

// which keeps parser tables smaller.

//

// The token values assigned to these symbols is determined by the order

// in which lemon first sees them.  It must be the case that ISNULL/NOTNULL,

// NE/EQ, GT/LE, and GE/LT are separated by only a single value.  See

// the sqlite3ExprIfFalse() routine for additional information on this

// constraint.

//

%left OR.

%left AND.

%right NOT.

%left IS MATCH LIKE_KW BETWEEN IN ISNULL NOTNULL NE EQ.

%left GT LE LT GE.

%right ESCAPE.

%left BITAND BITOR LSHIFT RSHIFT.

%left PLUS MINUS.

%left STAR SLASH REM.

%left CONCAT.

%right UMINUS UPLUS BITNOT.

// And "ids" is an identifer-or-string.

//

%type ids {Token}

ids(A) ::= ID|STRING(X).   {A = X;}

// The name of a column or table can be any of the following:

//

%type nm {Token}

nm(A) ::= ID(X).         {A = X;}

nm(A) ::= STRING(X).     {A = X;}

nm(A) ::= JOIN_KW(X).    {A = X;}

// A typetoken is really one or more tokens that form a type name such

// as can be found after the column name in a CREATE TABLE statement.

// Multiple tokens are concatenated to form the value of the typetoken.

//

%type typetoken {Token}

type ::= .

type ::= typetoken(X).                   {sqlite3AddColumnType(pParse,&X);}

typetoken(A) ::= typename(X).   {A = X;}

typetoken(A) ::= typename(X) LP signed RP(Y). {

  A.z = X.z;

  A.n = &Y.z[Y.n] - X.z;

}

typetoken(A) ::= typename(X) LP signed COMMA signed RP(Y). {

  A.z = X.z;

  A.n = &Y.z[Y.n] - X.z;

}

%type typename {Token}

typename(A) ::= ids(X).             {A = X;}

typename(A) ::= typename(X) ids(Y). {A.z=X.z; A.n=Y.n+(Y.z-X.z);}

%type signed {int}

signed(A) ::= plus_num(X).    { A = atoi((char*)X.z); }

signed(A) ::= minus_num(X).   { A = -atoi((char*)X.z); }

// "carglist" is a list of additional constraints that come after the

// column name and column type in a CREATE TABLE statement.

//

carglist ::= carglist carg.

carglist ::= .

carg ::= CONSTRAINT nm ccons.

carg ::= ccons.

carg ::= DEFAULT term(X).            {sqlite3AddDefaultValue(pParse,X);}

carg ::= DEFAULT LP expr(X) RP.      {sqlite3AddDefaultValue(pParse,X);}

carg ::= DEFAULT PLUS term(X).       {sqlite3AddDefaultValue(pParse,X);}

carg ::= DEFAULT MINUS term(X).      {

  Expr *p = sqlite3Expr(TK_UMINUS, X, 0, 0);

  sqlite3AddDefaultValue(pParse,p);

}

carg ::= DEFAULT id(X).              {

  Expr *p = sqlite3Expr(TK_STRING, 0, 0, &X);

  sqlite3AddDefaultValue(pParse,p);

}

// In addition to the type name, we also care about the primary key and

// UNIQUE constraints.

//

ccons ::= NULL onconf.

ccons ::= NOT NULL onconf(R).               {sqlite3AddNotNull(pParse, R);}

ccons ::= PRIMARY KEY sortorder(Z) onconf(R) autoinc(I).

                                     {sqlite3AddPrimaryKey(pParse,0,R,I,Z);}

ccons ::= UNIQUE onconf(R).    {sqlite3CreateIndex(pParse,0,0,0,0,R,0,0,0,0);}

ccons ::= CHECK LP expr(X) RP.       {sqlite3AddCheckConstraint(pParse,X);}

ccons ::= REFERENCES nm(T) idxlist_opt(TA) refargs(R).

                                {sqlite3CreateForeignKey(pParse,0,&T,TA,R);}

ccons ::= defer_subclause(D).   {sqlite3DeferForeignKey(pParse,D);}

ccons ::= COLLATE id(C).  {sqlite3AddCollateType(pParse, (char*)C.z, C.n);}

// The optional AUTOINCREMENT keyword

%type autoinc {int}

autoinc(X) ::= .          {X = 0;}

autoinc(X) ::= AUTOINCR.  {X = 1;}

// The next group of rules parses the arguments to a REFERENCES clause

// that determine if the referential integrity checking is deferred or

// or immediate and which determine what action to take if a ref-integ

// check fails.

//

%type refargs {int}

refargs(A) ::= .                     { A = OE_Restrict * 0x010101; }

refargs(A) ::= refargs(X) refarg(Y). { A = (X & Y.mask) | Y.value; }

%type refarg {struct {int value; int mask;}}

refarg(A) ::= MATCH nm.              { A.value = 0;     A.mask = 0x000000; }

refarg(A) ::= ON DELETE refact(X).   { A.value = X;     A.mask = 0x0000ff; }

refarg(A) ::= ON UPDATE refact(X).   { A.value = X<<8;  A.mask = 0x00ff00; }

refarg(A) ::= ON INSERT refact(X).   { A.value = X<<16; A.mask = 0xff0000; }

%type refact {int}

refact(A) ::= SET NULL.              { A = OE_SetNull; }

refact(A) ::= SET DEFAULT.           { A = OE_SetDflt; }

refact(A) ::= CASCADE.               { A = OE_Cascade; }

refact(A) ::= RESTRICT.              { A = OE_Restrict; }

%type defer_subclause {int}

defer_subclause(A) ::= NOT DEFERRABLE init_deferred_pred_opt(X).  {A = X;}

defer_subclause(A) ::= DEFERRABLE init_deferred_pred_opt(X).      {A = X;}

%type init_deferred_pred_opt {int}

init_deferred_pred_opt(A) ::= .                       {A = 0;}

init_deferred_pred_opt(A) ::= INITIALLY DEFERRED.     {A = 1;}

init_deferred_pred_opt(A) ::= INITIALLY IMMEDIATE.    {A = 0;}

// For the time being, the only constraint we care about is the primary

// key and UNIQUE.  Both create indices.

//

conslist_opt(A) ::= .                   {A.n = 0; A.z = 0;}

conslist_opt(A) ::= COMMA(X) conslist.  {A = X;}

conslist ::= conslist COMMA tcons.

conslist ::= conslist tcons.

conslist ::= tcons.

tcons ::= CONSTRAINT nm.

tcons ::= PRIMARY KEY LP idxlist(X) autoinc(I) RP onconf(R).

                                         {sqlite3AddPrimaryKey(pParse,X,R,I,0);}

tcons ::= UNIQUE LP idxlist(X) RP onconf(R).

                                 {sqlite3CreateIndex(pParse,0,0,0,X,R,0,0,0,0);}

tcons ::= CHECK LP expr(E) RP onconf. {sqlite3AddCheckConstraint(pParse,E);}

tcons ::= FOREIGN KEY LP idxlist(FA) RP

          REFERENCES nm(T) idxlist_opt(TA) refargs(R) defer_subclause_opt(D). {

    sqlite3CreateForeignKey(pParse, FA, &T, TA, R);

    sqlite3DeferForeignKey(pParse, D);

}

%type defer_subclause_opt {int}

defer_subclause_opt(A) ::= .                    {A = 0;}

defer_subclause_opt(A) ::= defer_subclause(X).  {A = X;}

// The following is a non-standard extension that allows us to declare the

// default behavior when there is a constraint conflict.

//

%type onconf {int}

%type orconf {int}

%type resolvetype {int}

onconf(A) ::= .                              {A = OE_Default;}

onconf(A) ::= ON CONFLICT resolvetype(X).    {A = X;}

orconf(A) ::= .                              {A = OE_Default;}

orconf(A) ::= OR resolvetype(X).             {A = X;}

resolvetype(A) ::= raisetype(X).             {A = X;}

resolvetype(A) ::= IGNORE.                   {A = OE_Ignore;}

resolvetype(A) ::= REPLACE.                  {A = OE_Replace;}

////////////////////////// The DROP TABLE /////////////////////////////////////

//

cmd ::= DROP TABLE ifexists(E) fullname(X). {

  sqlite3DropTable(pParse, X, 0, E);

}

%type ifexists {int}

ifexists(A) ::= IF EXISTS.   {A = 1;}

ifexists(A) ::= .            {A = 0;}

///////////////////// The CREATE VIEW statement /////////////////////////////

//

%ifndef SQLITE_OMIT_VIEW

cmd ::= CREATE(X) temp(T) VIEW nm(Y) dbnm(Z) AS select(S). {

  sqlite3CreateView(pParse, &X, &Y, &Z, S, T);

}

cmd ::= DROP VIEW ifexists(E) fullname(X). {

  sqlite3DropTable(pParse, X, 1, E);

}

%endif // SQLITE_OMIT_VIEW

//////////////////////// The SELECT statement /////////////////////////////////

//

cmd ::= select(X).  {

  sqlite3Select(pParse, X, SRT_Callback, 0, 0, 0, 0, 0);

  sqlite3SelectDelete(X);

}

%type select {Select*}

%destructor select {sqlite3SelectDelete($$);}

%type oneselect {Select*}

%destructor oneselect {sqlite3SelectDelete($$);}

select(A) ::= oneselect(X).                      {A = X;}

%ifndef SQLITE_OMIT_COMPOUND_SELECT

select(A) ::= select(X) multiselect_op(Y) oneselect(Z).  {

  if( Z ){

    Z->op = Y;

    Z->pPrior = X;

  }

  A = Z;

}

%type multiselect_op {int}

multiselect_op(A) ::= UNION(OP).             {A = @OP;}

multiselect_op(A) ::= UNION ALL.             {A = TK_ALL;}

multiselect_op(A) ::= EXCEPT|INTERSECT(OP).  {A = @OP;}

%endif // SQLITE_OMIT_COMPOUND_SELECT

oneselect(A) ::= SELECT distinct(D) selcollist(W) from(X) where_opt(Y)

                 groupby_opt(P) having_opt(Q) orderby_opt(Z) limit_opt(L). {

  A = sqlite3SelectNew(W,X,Y,P,Q,Z,D,L.pLimit,L.pOffset);

}

// The "distinct" nonterminal is true (1) if the DISTINCT keyword is

// present and false (0) if it is not.

//

%type distinct {int}

distinct(A) ::= DISTINCT.   {A = 1;}

distinct(A) ::= ALL.        {A = 0;}

distinct(A) ::= .           {A = 0;}

// selcollist is a list of expressions that are to become the return

// values of the SELECT statement.  The "*" in statements like

// "SELECT * FROM ..." is encoded as a special expression with an

// opcode of TK_ALL.

//

%type selcollist {ExprList*}

%destructor selcollist {sqlite3ExprListDelete($$);}

%type sclp {ExprList*}

%destructor sclp {sqlite3ExprListDelete($$);}

sclp(A) ::= selcollist(X) COMMA.             {A = X;}

sclp(A) ::= .                                {A = 0;}

selcollist(A) ::= sclp(P) expr(X) as(Y).     {

   A = sqlite3ExprListAppend(P,X,Y.n?&Y:0);

}

selcollist(A) ::= sclp(P) STAR. {

  A = sqlite3ExprListAppend(P, sqlite3Expr(TK_ALL, 0, 0, 0), 0);

}

selcollist(A) ::= sclp(P) nm(X) DOT STAR. {

  Expr *pRight = sqlite3Expr(TK_ALL, 0, 0, 0);

  Expr *pLeft = sqlite3Expr(TK_ID, 0, 0, &X);

  A = sqlite3ExprListAppend(P, sqlite3Expr(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 nm(Y).    {X = Y;}

as(X) ::= ids(Y).      {X = Y;}

as(X) ::= .            {X.n = 0;}

%type seltablist {SrcList*}

%destructor seltablist {sqlite3SrcListDelete($$);}

%type stl_prefix {SrcList*}

%destructor stl_prefix {sqlite3SrcListDelete($$);}

%type from {SrcList*}

%destructor from {sqlite3SrcListDelete($$);}

// 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) nm(Y) dbnm(D) as(Z) on_opt(N) using_opt(U). {

  A = sqlite3SrcListAppend(X,&Y,&D);

  if( Z.n ) sqlite3SrcListAddAlias(A,&Z);

  if( N ){

    if( A && A->nSrc>1 ){ A->a[A->nSrc-2].pOn = N; }

    else { sqlite3ExprDelete(N); }

  }

  if( U ){

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

    else { sqlite3IdListDelete(U); }

  }

}

%ifndef SQLITE_OMIT_SUBQUERY

  seltablist(A) ::= stl_prefix(X) LP seltablist_paren(S) RP

                    as(Z) on_opt(N) using_opt(U). {

    A = sqlite3SrcListAppend(X,0,0);

    A->a[A->nSrc-1].pSelect = S;

    if( Z.n ) sqlite3SrcListAddAlias(A,&Z);

    if( N ){

      if( A && A->nSrc>1 ){ A->a[A->nSrc-2].pOn = N; }

      else { sqlite3ExprDelete(N); }

    }

    if( U ){

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

      else { sqlite3IdListDelete(U); }

    }

  }

  // A seltablist_paren nonterminal represents anything in a FROM that

  // is contained inside parentheses.  This can be either a subquery or

  // a grouping of table and subqueries.

  //

  %type seltablist_paren {Select*}

  %destructor seltablist_paren {sqlite3SelectDelete($$);}

  seltablist_paren(A) ::= select(S).      {A = S;}

  seltablist_paren(A) ::= seltablist(F).  {

     A = sqlite3SelectNew(0,F,0,0,0,0,0,0,0);

  }

%endif // SQLITE_OMIT_SUBQUERY

%type dbnm {Token}

dbnm(A) ::= .          {A.z=0; A.n=0;}

dbnm(A) ::= DOT nm(X). {A = X;}

%type fullname {SrcList*}

%destructor fullname {sqlite3SrcListDelete($$);}

fullname(A) ::= nm(X) dbnm(Y).  {A = sqlite3SrcListAppend(0,&X,&Y);}

%type joinop {int}

%type joinop2 {int}

joinop(X) ::= COMMA|JOIN.              { X = JT_INNER; }

joinop(X) ::= JOIN_KW(A) JOIN.         { X = sqlite3JoinType(pParse,&A,0,0); }

joinop(X) ::= JOIN_KW(A) nm(B) JOIN.   { X = sqlite3JoinType(pParse,&A,&B,0); }

joinop(X) ::= JOIN_KW(A) nm(B) nm(C) JOIN.

                                       { X = sqlite3JoinType(pParse,&A,&B,&C); }

%type on_opt {Expr*}

%destructor on_opt {sqlite3ExprDelete($$);}

on_opt(N) ::= ON expr(E).   {N = E;}

on_opt(N) ::= .             {N = 0;}

%type using_opt {IdList*}

%destructor using_opt {sqlite3IdListDelete($$);}

using_opt(U) ::= USING LP inscollist(L) RP.  {U = L;}

using_opt(U) ::= .                        {U = 0;}

%type orderby_opt {ExprList*}

%destructor orderby_opt {sqlite3ExprListDelete($$);}

%type sortlist {ExprList*}

%destructor sortlist {sqlite3ExprListDelete($$);}

%type sortitem {Expr*}