/*

 ** 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 C code routines that are called by the parser

 ** to handle SELECT statements in SQLite.

 **

 ** $Id$

 */

 #include "sqliteInt.h"

 /*

 ** Delete all the content of a Select structure but do not deallocate

 ** the select structure itself.

 */

 static void clearSelect(Select *p){

   sqlite3ExprListDelete(p->pEList);

   sqlite3SrcListDelete(p->pSrc);

   sqlite3ExprDelete(p->pWhere);

   sqlite3ExprListDelete(p->pGroupBy);

   sqlite3ExprDelete(p->pHaving);

   sqlite3ExprListDelete(p->pOrderBy);

   sqlite3SelectDelete(p->pPrior);

   sqlite3ExprDelete(p->pLimit);

   sqlite3ExprDelete(p->pOffset);

 }

 /*

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

 ** structure.

 */

 Select *sqlite3SelectNew(

   Parse *pParse,        /* Parsing context */

   ExprList *pEList,     /* which columns to include in the result */

   SrcList *pSrc,        /* the FROM clause -- which tables to scan */

   Expr *pWhere,         /* the WHERE clause */

   ExprList *pGroupBy,   /* the GROUP BY clause */

   Expr *pHaving,        /* the HAVING clause */

   ExprList *pOrderBy,   /* the ORDER BY clause */

   int isDistinct,       /* true if the DISTINCT keyword is present */

   Expr *pLimit,         /* LIMIT value.  NULL means not used */

   Expr *pOffset         /* OFFSET value.  NULL means no offset */

 ){

   Select *pNew;

   Select standin;

   sqlite3 *db = pParse->db;

   pNew = sqlite3DbMallocZero(db, sizeof(*pNew) );

   assert( !pOffset || pLimit );   /* Can't have OFFSET without LIMIT. */

   if( pNew==0 ){

     pNew = &standin;

     memset(pNew, 0, sizeof(*pNew));

   }

   if( pEList==0 ){

     pEList = sqlite3ExprListAppend(pParse, 0, sqlite3Expr(db,TK_ALL,0,0,0), 0);

   }

   pNew->pEList = pEList;

   pNew->pSrc = pSrc;

   pNew->pWhere = pWhere;

   pNew->pGroupBy = pGroupBy;

   pNew->pHaving = pHaving;

   pNew->pOrderBy = pOrderBy;

   pNew->isDistinct = isDistinct;

   pNew->op = TK_SELECT;

   assert( pOffset==0 || pLimit!=0 );

   pNew->pLimit = pLimit;

   pNew->pOffset = pOffset;

   pNew->iLimit = -1;

   pNew->iOffset = -1;

   pNew->addrOpenEphm[0] = -1;

   pNew->addrOpenEphm[1] = -1;

   pNew->addrOpenEphm[2] = -1;

   if( pNew==&standin) {

     clearSelect(pNew);

     pNew = 0;

   }

   return pNew;

 }

 /*

 ** Delete the given Select structure and all of its substructures.

 */

 void sqlite3SelectDelete(Select *p){

   if( p ){

     clearSelect(p);

     sqlite3_free(p);

   }

 }

 /*

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

 **     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 sqlite3JoinType(Parse *pParse, Token *pA, Token *pB, Token *pC){

   int jointype = 0;

   Token *apAll[3];

   Token *p;

   static const struct {

     const char zKeyword[8];

     u8 nChar;

     u8 code;

   } keywords[] = {

     { "natural", 7, JT_NATURAL },

     { "left",    4, JT_LEFT|JT_OUTER },

     { "right",   5, JT_RIGHT|JT_OUTER },

     { "full",    4, JT_LEFT|JT_RIGHT|JT_OUTER },

     { "outer",   5, JT_OUTER },

     { "inner",   5, JT_INNER },

     { "cross",   5, JT_INNER|JT_CROSS },

   };

   int i, j;

   apAll[0] = pA;

   apAll[1] = pB;

   apAll[2] = pC;

   for(i=0; i<3 && apAll[i]; i++){

     p = apAll[i];

     for(j=0; j<sizeof(keywords)/sizeof(keywords[0]); j++){

       if( p->n==keywords[j].nChar 

           && sqlite3StrNICmp((char*)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|JT_OUTER))==(JT_INNER|JT_OUTER) ||

      (jointype & JT_ERROR)!=0

   ){

     const char *zSp1 = " ";

     const char *zSp2 = " ";

     if( pB==0 ){ zSp1++; }

     if( pC==0 ){ zSp2++; }

     sqlite3ErrorMsg(pParse, "unknown or unsupported join type: "

        "%T%s%T%s%T", pA, zSp1, pB, zSp2, pC);

     jointype = JT_INNER;

   }else if( jointype & JT_RIGHT ){

     sqlite3ErrorMsg(pParse, 

       "RIGHT and FULL OUTER JOINs are not currently supported");

     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( sqlite3StrICmp(pTab->aCol[i].zName, zCol)==0 ) return i;

   }

   return -1;

 }

 /*

 ** Set the value of a token to a '\000'-terminated string.

 */

 static void setToken(Token *p, const char *z){

   p->z = (u8*)z;

   p->n = z ? strlen(z) : 0;

   p->dyn = 0;

 }

 /*

 ** Set the token to the double-quoted and escaped version of the string pointed

 ** to by z. For example;

 **

 **    {a"bc}  ->  {"a""bc"}

 */

 static void setQuotedToken(Parse *pParse, Token *p, const char *z){

   p->z = (u8 *)sqlite3MPrintf(0, "\"%w\"", z);

   p->dyn = 1;

   if( p->z ){

     p->n = strlen((char *)p->z);

   }else{

     pParse->db->mallocFailed = 1;

   }

 }

 /*

 ** Create an expression node for an identifier with the name of zName

 */

 Expr *sqlite3CreateIdExpr(Parse *pParse, const char *zName){

   Token dummy;

   setToken(&dummy, zName);

   return sqlite3PExpr(pParse, TK_ID, 0, 0, &dummy);

 }

 /*

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

   Parse *pParse,           /* Parsing context */

   const char *zCol,        /* Name of the column */

   const Table *pTab1,      /* First table */

   const char *zAlias1,     /* Alias for first table.  May be NULL */

   const Table *pTab2,      /* Second table */

   const char *zAlias2,     /* Alias for second table.  May be NULL */

   int iRightJoinTable,     /* VDBE cursor for the right table */

   Expr **ppExpr            /* Add the equality term to this expression */

 ){

   Expr *pE1a, *pE1b, *pE1c;

   Expr *pE2a, *pE2b, *pE2c;

   Expr *pE;

   pE1a = sqlite3CreateIdExpr(pParse, zCol);

   pE2a = sqlite3CreateIdExpr(pParse, zCol);

   if( zAlias1==0 ){

     zAlias1 = pTab1->zName;

   }

   pE1b = sqlite3CreateIdExpr(pParse, zAlias1);

   if( zAlias2==0 ){

     zAlias2 = pTab2->zName;

   }

   pE2b = sqlite3CreateIdExpr(pParse, zAlias2);

   pE1c = sqlite3PExpr(pParse, TK_DOT, pE1b, pE1a, 0);

   pE2c = sqlite3PExpr(pParse, TK_DOT, pE2b, pE2a, 0);

   pE = sqlite3PExpr(pParse, TK_EQ, pE1c, pE2c, 0);

   if( pE ){

     ExprSetProperty(pE, EP_FromJoin);

     pE->iRightJoinTable = iRightJoinTable;

   }

   pE = sqlite3ExprAnd(pParse->db,*ppExpr, pE);

   if( pE ){

     *ppExpr = pE;

   }

 }

 /*

 ** Set the EP_FromJoin property on all terms of the given expression.

 ** And set the Expr.iRightJoinTable to iTable for every term in the

 ** expression.

 **

 ** The EP_FromJoin property is used on terms of an expression to tell

 ** the LEFT OUTER JOIN processing logic that this term is part of the

 ** join restriction specified in the ON or USING clause and not a part

 ** of the more general WHERE clause.  These terms are moved over to the

 ** WHERE clause during join processing but we need to remember that they

 ** originated in the ON or USING clause.

 **

 ** The Expr.iRightJoinTable tells the WHERE clause processing that the

 ** expression depends on table iRightJoinTable even if that table is not

 ** explicitly mentioned in the expression.  That information is needed

 ** for cases like this:

 **

 **    SELECT * FROM t1 LEFT JOIN t2 ON t1.a=t2.b AND t1.x=5

 **

 ** The where clause needs to defer the handling of the t1.x=5

 ** term until after the t2 loop of the join.  In that way, a

 ** NULL t2 row will be inserted whenever t1.x!=5.  If we do not

 ** defer the handling of t1.x=5, it will be processed immediately

 ** after the t1 loop and rows with t1.x!=5 will never appear in

 ** the output, which is incorrect.

 */

 static void setJoinExpr(Expr *p, int iTable){

   while( p ){

     ExprSetProperty(p, EP_FromJoin);

     p->iRightJoinTable = iTable;

     setJoinExpr(p->pLeft, iTable);

     p = p->pRight;

   } 

 }

 /*

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

 **

 ** The terms of a FROM clause are contained in the Select.pSrc structure.

 ** The left most table is the first entry in Select.pSrc.  The right-most

 ** table is the last entry.  The join operator is held in the entry to

 ** the left.  Thus entry 0 contains the join operator for the join between

 ** entries 0 and 1.  Any ON or USING clauses associated with the join are

 ** also attached to the left entry.

 **

 ** This routine returns the number of errors encountered.

 */

 static int sqliteProcessJoin(Parse *pParse, Select *p){

   SrcList *pSrc;                  /* All tables in the FROM clause */

   int i, j;                       /* Loop counters */

   struct SrcList_item *pLeft;     /* Left table being joined */

   struct SrcList_item *pRight;    /* Right table being joined */

   pSrc = p->pSrc;

   pLeft = &pSrc->a[0];

   pRight = &pLeft[1];

   for(i=0; i<pSrc->nSrc-1; i++, pRight++, pLeft++){

     Table *pLeftTab = pLeft->pTab;

     Table *pRightTab = pRight->pTab;

     if( pLeftTab==0 || pRightTab==0 ) continue;

     /* When the NATURAL keyword is present, add WHERE clause terms for

     ** every column that the two tables have in common.

     */

     if( pRight->jointype & JT_NATURAL ){

       if( pRight->pOn || pRight->pUsing ){

         sqlite3ErrorMsg(pParse, "a NATURAL join may not have "

            "an ON or USING clause", 0);

         return 1;

       }

       for(j=0; j<pLeftTab->nCol; j++){

         char *zName = pLeftTab->aCol[j].zName;

         if( columnIndex(pRightTab, zName)>=0 ){

           addWhereTerm(pParse, zName, pLeftTab, pLeft->zAlias, 

                               pRightTab, pRight->zAlias,

                               pRight->iCursor, &p->pWhere);

         }

       }

     }

     /* Disallow both ON and USING clauses in the same join

     */

     if( pRight->pOn && pRight->pUsing ){

       sqlite3ErrorMsg(pParse, "cannot have both ON and USING "

         "clauses in the same join");

       return 1;

     }

     /* Add the ON clause to the end of the WHERE clause, connected by

     ** an AND operator.

     */

     if( pRight->pOn ){

       setJoinExpr(pRight->pOn, pRight->iCursor);

       p->pWhere = sqlite3ExprAnd(pParse->db, p->pWhere, pRight->pOn);

       pRight->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( pRight->pUsing ){

       IdList *pList = pRight->pUsing;

       for(j=0; j<pList->nId; j++){

         char *zName = pList->a[j].zName;

         if( columnIndex(pLeftTab, zName)<0 || columnIndex(pRightTab, zName)<0 ){

           sqlite3ErrorMsg(pParse, "cannot join using column %s - column "

             "not present in both tables", zName);

           return 1;

         }

         addWhereTerm(pParse, zName, pLeftTab, pLeft->zAlias, 

                             pRightTab, pRight->zAlias,

                             pRight->iCursor, &p->pWhere);

       }

     }

   }

   return 0;

 }

 /*

 ** Insert code into "v" that will push the record on the top of the

 ** stack into the sorter.

 */

 static void pushOntoSorter(

   Parse *pParse,         /* Parser context */

   ExprList *pOrderBy,    /* The ORDER BY clause */

   Select *pSelect        /* The whole SELECT statement */

 ){

   Vdbe *v = pParse->pVdbe;

   sqlite3ExprCodeExprList(pParse, pOrderBy);

   sqlite3VdbeAddOp(v, OP_Sequence, pOrderBy->iECursor, 0);

   sqlite3VdbeAddOp(v, OP_Pull, pOrderBy->nExpr + 1, 0);

   sqlite3VdbeAddOp(v, OP_MakeRecord, pOrderBy->nExpr + 2, 0);

   sqlite3VdbeAddOp(v, OP_IdxInsert, pOrderBy->iECursor, 0);

   if( pSelect->iLimit>=0 ){

     int addr1, addr2;

     addr1 = sqlite3VdbeAddOp(v, OP_IfMemZero, pSelect->iLimit+1, 0);

     sqlite3VdbeAddOp(v, OP_MemIncr, -1, pSelect->iLimit+1);

     addr2 = sqlite3VdbeAddOp(v, OP_Goto, 0, 0);

     sqlite3VdbeJumpHere(v, addr1);

     sqlite3VdbeAddOp(v, OP_Last, pOrderBy->iECursor, 0);

     sqlite3VdbeAddOp(v, OP_Delete, pOrderBy->iECursor, 0);

     sqlite3VdbeJumpHere(v, addr2);

     pSelect->iLimit = -1;

   }

 }

 /*

 ** Add code to implement the OFFSET

 */

 static void codeOffset(

   Vdbe *v,          /* Generate code into this VM */

   Select *p,        /* The SELECT statement being coded */

   int iContinue,    /* Jump here to skip the current record */

   int nPop          /* Number of times to pop stack when jumping */

 ){

   if( p->iOffset>=0 && iContinue!=0 ){

     int addr;

     sqlite3VdbeAddOp(v, OP_MemIncr, -1, p->iOffset);

     addr = sqlite3VdbeAddOp(v, OP_IfMemNeg, p->iOffset, 0);

     if( nPop>0 ){

       sqlite3VdbeAddOp(v, OP_Pop, nPop, 0);

     }

     sqlite3VdbeAddOp(v, OP_Goto, 0, iContinue);

     VdbeComment((v, "# skip OFFSET records"));

     sqlite3VdbeJumpHere(v, addr);

   }

 }

 /*

 ** Add code that will check to make sure the top N elements of the

 ** stack are distinct.  iTab is a sorting index that holds previously

 ** seen combinations of the N values.  A new entry is made in iTab

 ** if the current N values are new.

 **

 ** A jump to addrRepeat is made and the N+1 values are popped from the

 ** stack if the top N elements are not distinct.

 */

 static void codeDistinct(

   Vdbe *v,           /* Generate code into this VM */

   int iTab,          /* A sorting index used to test for distinctness */

   int addrRepeat,    /* Jump to here if not distinct */

   int N              /* The top N elements of the stack must be distinct */

 ){

   sqlite3VdbeAddOp(v, OP_MakeRecord, -N, 0);

   sqlite3VdbeAddOp(v, OP_Distinct, iTab, sqlite3VdbeCurrentAddr(v)+3);

   sqlite3VdbeAddOp(v, OP_Pop, N+1, 0);

   sqlite3VdbeAddOp(v, OP_Goto, 0, addrRepeat);

   VdbeComment((v, "# skip indistinct records"));

   sqlite3VdbeAddOp(v, OP_IdxInsert, iTab, 0);

 }

 /*

 ** Generate an error message when a SELECT is used within a subexpression

 ** (example:  "a IN (SELECT * FROM table)") but it has more than 1 result

 ** column.  We do this in a subroutine because the error occurs in multiple

 ** places.

 */

 static int checkForMultiColumnSelectError(Parse *pParse, int eDest, int nExpr){

   if( nExpr>1 && (eDest==SRT_Mem || eDest==SRT_Set) ){

     sqlite3ErrorMsg(pParse, "only a single result allowed for "

        "a SELECT that is part of an expression");

     return 1;

   }else{

     return 0;

   }

 }

 /*

 ** This routine generates the code for the inside of the inner loop

 ** of a SELECT.

 **

 ** If srcTab and nColumn are both zero, then the pEList expressions

 ** are evaluated in order to get the data for this row.  If nColumn>0

 ** then data is pulled from srcTab and pEList is used only to get the

 ** datatypes for each column.

 */

 static int selectInnerLoop(

   Parse *pParse,          /* The parser context */

   Select *p,              /* The complete select statement being coded */

   ExprList *pEList,       /* List of values being extracted */

   int srcTab,             /* Pull data from this table */

   int nColumn,            /* Number of columns in the source table */

   ExprList *pOrderBy,     /* If not NULL, sort results using this key */

   int distinct,           /* If >=0, make sure results are distinct */

   int eDest,              /* How to dispose of the results */

   int iParm,              /* An argument to the disposal method */

   int iContinue,          /* Jump here to continue with next row */

   int iBreak,             /* Jump here to break out of the inner loop */

   char *aff               /* affinity string if eDest is SRT_Union */

 ){

   Vdbe *v = pParse->pVdbe;

   int i;

   int hasDistinct;        /* True if the DISTINCT keyword is present */

   if( v==0 ) return 0;

   assert( pEList!=0 );

   /* If there was a LIMIT clause on the SELECT statement, then do the check

   ** to see if this row should be output.

   */

   hasDistinct = distinct>=0 && pEList->nExpr>0;

   if( pOrderBy==0 && !hasDistinct ){

     codeOffset(v, p, iContinue, 0);

   }

   /* Pull the requested columns.

   */

   if( nColumn>0 ){

     for(i=0; i<nColumn; i++){

       sqlite3VdbeAddOp(v, OP_Column, srcTab, i);

     }

   }else{

     nColumn = pEList->nExpr;

     sqlite3ExprCodeExprList(pParse, pEList);

   }

   /* If the DISTINCT keyword was present on the SELECT statement

   ** and this row has been seen before, then do not make this row

   ** part of the result.

   */

   if( hasDistinct ){

     assert( pEList!=0 );

     assert( pEList->nExpr==nColumn );

     codeDistinct(v, distinct, iContinue, nColumn);

     if( pOrderBy==0 ){

       codeOffset(v, p, iContinue, nColumn);

     }

   }

   if( checkForMultiColumnSelectError(pParse, eDest, pEList->nExpr) ){

     return 0;

   }

   switch( eDest ){

     /* In this mode, write each query result to the key of the temporary

     ** table iParm.

     */

 #ifndef SQLITE_OMIT_COMPOUND_SELECT

     case SRT_Union: {

       sqlite3VdbeAddOp(v, OP_MakeRecord, nColumn, 0);

       if( aff ){

         sqlite3VdbeChangeP3(v, -1, aff, P3_STATIC);

       }

       sqlite3VdbeAddOp(v, OP_IdxInsert, iParm, 0);

       break;

     }

     /* Construct a record from the query result, but instead of

     ** saving that record, use it as a key to delete elements from

     ** the temporary table iParm.

     */

     case SRT_Except: {

       int addr;

       addr = sqlite3VdbeAddOp(v, OP_MakeRecord, nColumn, 0);

       sqlite3VdbeChangeP3(v, -1, aff, P3_STATIC);

       sqlite3VdbeAddOp(v, OP_NotFound, iParm, addr+3);

       sqlite3VdbeAddOp(v, OP_Delete, iParm, 0);

       break;

     }

 #endif

     /* Store the result as data using a unique key.

     */

     case SRT_Table:

     case SRT_EphemTab: {

       sqlite3VdbeAddOp(v, OP_MakeRecord, nColumn, 0);

       if( pOrderBy ){

         pushOntoSorter(pParse, pOrderBy, p);

       }else{

         sqlite3VdbeAddOp(v, OP_NewRowid, iParm, 0);

         sqlite3VdbeAddOp(v, OP_Pull, 1, 0);

         sqlite3VdbeAddOp(v, OP_Insert, iParm, OPFLAG_APPEND);

       }

       break;

     }

 #ifndef SQLITE_OMIT_SUBQUERY

     /* If we are creating a set for an "expr IN (SELECT ...)" construct,

     ** then there should be a single item on the stack.  Write this

     ** item into the set table with bogus data.

     */

     case SRT_Set: {

       int addr1 = sqlite3VdbeCurrentAddr(v);

       int addr2;

       assert( nColumn==1 );

       sqlite3VdbeAddOp(v, OP_NotNull, -1, addr1+3);

       sqlite3VdbeAddOp(v, OP_Pop, 1, 0);

       addr2 = sqlite3VdbeAddOp(v, OP_Goto, 0, 0);

       p->affinity = sqlite3CompareAffinity(pEList->a[0].pExpr,(iParm>>16)&0xff);

       if( pOrderBy ){

         /* At first glance you would think we could optimize out the

         ** ORDER BY in this case since the order of entries in the set

         ** does not matter.  But there might be a LIMIT clause, in which

         ** case the order does matter */

         pushOntoSorter(pParse, pOrderBy, p);

       }else{

         sqlite3VdbeOp3(v, OP_MakeRecord, 1, 0, &p->affinity, 1);

         sqlite3VdbeAddOp(v, OP_IdxInsert, (iParm&0x0000FFFF), 0);

       }

       sqlite3VdbeJumpHere(v, addr2);

       break;

     }

     /* If any row exist in the result set, record that fact and abort.

     */

     case SRT_Exists: {

       sqlite3VdbeAddOp(v, OP_MemInt, 1, iParm);

       sqlite3VdbeAddOp(v, OP_Pop, nColumn, 0);

       /* The LIMIT clause will terminate the loop for us */

       break;

     }

     /* If this is a scalar select that is part of an expression, then

     ** store the results in the appropriate memory cell and break out

     ** of the scan loop.

     */

     case SRT_Mem: {

       assert( nColumn==1 );

       if( pOrderBy ){

         pushOntoSorter(pParse, pOrderBy, p);

       }else{

         sqlite3VdbeAddOp(v, OP_MemStore, iParm, 1);

         /* The LIMIT clause will jump out of the loop for us */

       }

       break;

     }

 #endif /* #ifndef SQLITE_OMIT_SUBQUERY */

     /* Send the data to the callback function or to a subroutine.  In the

     ** case of a subroutine, the subroutine itself is responsible for

     ** popping the data from the stack.

     */

     case SRT_Subroutine:

     case SRT_Callback: {

       if( pOrderBy ){

         sqlite3VdbeAddOp(v, OP_MakeRecord, nColumn, 0);

         pushOntoSorter(pParse, pOrderBy, p);

       }else if( eDest==SRT_Subroutine ){

         sqlite3VdbeAddOp(v, OP_Gosub, 0, iParm);

       }else{

         sqlite3VdbeAddOp(v, OP_Callback, nColumn, 0);

       }

       break;

     }

 #if !defined(SQLITE_OMIT_TRIGGER)

     /* Discard the results.  This is used for SELECT statements inside

     ** the body of a TRIGGER.  The purpose of such selects is to call

     ** user-defined functions that have side effects.  We do not care

     ** about the actual results of the select.

     */

     default: {

       assert( eDest==SRT_Discard );

       sqlite3VdbeAddOp(v, OP_Pop, nColumn, 0);

       break;

     }

 #endif

   }

   /* Jump to the end of the loop if the LIMIT is reached.

   */

   if( p->iLimit>=0 && pOrderBy==0 ){

     sqlite3VdbeAddOp(v, OP_MemIncr, -1, p->iLimit);

     sqlite3VdbeAddOp(v, OP_IfMemZero, p->iLimit, iBreak);

   }

   return 0;

 }

 /*

 ** Given an expression list, generate a KeyInfo structure that records

 ** the collating sequence for each expression in that expression list.

 **

 ** If the ExprList is an ORDER BY or GROUP BY clause then the resulting

 ** KeyInfo structure is appropriate for initializing a virtual index to

 ** implement that clause.  If the ExprList is the result set of a SELECT

 ** then the KeyInfo structure is appropriate for initializing a virtual

 ** index to implement a DISTINCT test.

 **

 ** Space to hold the KeyInfo structure is obtain from malloc.  The calling

 ** function is responsible for seeing that this structure is eventually

 ** freed.  Add the KeyInfo structure to the P3 field of an opcode using

 ** P3_KEYINFO_HANDOFF is the usual way of dealing with this.

 */

 static KeyInfo *keyInfoFromExprList(Parse *pParse, ExprList *pList){

   sqlite3 *db = pParse->db;

   int nExpr;

   KeyInfo *pInfo;

   struct ExprList_item *pItem;

   int i;

   nExpr = pList->nExpr;

   pInfo = sqlite3DbMallocZero(db, sizeof(*pInfo) + nExpr*(sizeof(CollSeq*)+1) );

   if( pInfo ){

     pInfo->aSortOrder = (u8*)&pInfo->aColl[nExpr];

     pInfo->nField = nExpr;

     pInfo->enc = ENC(db);

     for(i=0, pItem=pList->a; i<nExpr; i++, pItem++){

       CollSeq *pColl;

       pColl = sqlite3ExprCollSeq(pParse, pItem->pExpr);

       if( !pColl ){

         pColl = db->pDfltColl;

       }

       pInfo->aColl[i] = pColl;

       pInfo->aSortOrder[i] = pItem->sortOrder;

     }

   }

   return pInfo;

 }

 /*

 ** If the inner loop was generated using a non-null pOrderBy argument,

 ** then the results were placed in a sorter.  After the loop is terminated

 ** we need to run the sorter and output the results.  The following

 ** routine generates the code needed to do that.

 */

 static void generateSortTail(

   Parse *pParse,   /* Parsing context */

   Select *p,       /* The SELECT statement */

   Vdbe *v,         /* Generate code into this VDBE */

   int nColumn,     /* Number of columns of data */

   int eDest,       /* Write the sorted results here */

   int iParm        /* Optional parameter associated with eDest */

 ){

   int brk = sqlite3VdbeMakeLabel(v);

   int cont = sqlite3VdbeMakeLabel(v);

   int addr;

   int iTab;

   int pseudoTab = 0;

   ExprList *pOrderBy = p->pOrderBy;

   iTab = pOrderBy->iECursor;

   if( eDest==SRT_Callback || eDest==SRT_Subroutine ){

     pseudoTab = pParse->nTab++;

     sqlite3VdbeAddOp(v, OP_OpenPseudo, pseudoTab, 0);

     sqlite3VdbeAddOp(v, OP_SetNumColumns, pseudoTab, nColumn);

   }

   addr = 1 + sqlite3VdbeAddOp(v, OP_Sort, iTab, brk);

   codeOffset(v, p, cont, 0);

   if( eDest==SRT_Callback || eDest==SRT_Subroutine ){

     sqlite3VdbeAddOp(v, OP_Integer, 1, 0);

   }

   sqlite3VdbeAddOp(v, OP_Column, iTab, pOrderBy->nExpr + 1);

   switch( eDest ){

     case SRT_Table:

     case SRT_EphemTab: {

       sqlite3VdbeAddOp(v, OP_NewRowid, iParm, 0);

       sqlite3VdbeAddOp(v, OP_Pull, 1, 0);

       sqlite3VdbeAddOp(v, OP_Insert, iParm, OPFLAG_APPEND);

       break;

     }

 #ifndef SQLITE_OMIT_SUBQUERY

     case SRT_Set: {

       assert( nColumn==1 );

       sqlite3VdbeAddOp(v, OP_NotNull, -1, sqlite3VdbeCurrentAddr(v)+3);

       sqlite3VdbeAddOp(v, OP_Pop, 1, 0);

       sqlite3VdbeAddOp(v, OP_Goto, 0, sqlite3VdbeCurrentAddr(v)+3);

       sqlite3VdbeOp3(v, OP_MakeRecord, 1, 0, &p->affinity, 1);

       sqlite3VdbeAddOp(v, OP_IdxInsert, (iParm&0x0000FFFF), 0);

       break;

     }

     case SRT_Mem: {

       assert( nColumn==1 );

       sqlite3VdbeAddOp(v, OP_MemStore, iParm, 1);

       /* The LIMIT clause will terminate the loop for us */

       break;

     }

 #endif

     case SRT_Callback:

     case SRT_Subroutine: {

       int i;

       sqlite3VdbeAddOp(v, OP_Insert, pseudoTab, 0);

       for(i=0; i<nColumn; i++){

         sqlite3VdbeAddOp(v, OP_Column, pseudoTab, i);

       }

       if( eDest==SRT_Callback ){

         sqlite3VdbeAddOp(v, OP_Callback, nColumn, 0);

       }else{

         sqlite3VdbeAddOp(v, OP_Gosub, 0, iParm);

       }

       break;

     }

     default: {

       /* Do nothing */

       break;

     }

   }

   /* Jump to the end of the loop when the LIMIT is reached

   */

   if( p->iLimit>=0 ){

     sqlite3VdbeAddOp(v, OP_MemIncr, -1, p->iLimit);

     sqlite3VdbeAddOp(v, OP_IfMemZero, p->iLimit, brk);

   }

   /* The bottom of the loop

   */

   sqlite3VdbeResolveLabel(v, cont);

   sqlite3VdbeAddOp(v, OP_Next, iTab, addr);

   sqlite3VdbeResolveLabel(v, brk);

   if( eDest==SRT_Callback || eDest==SRT_Subroutine ){

     sqlite3VdbeAddOp(v, OP_Close, pseudoTab, 0);

   }

 }

 /*

 ** Return a pointer to a string containing the 'declaration type' of the

 ** expression pExpr. The string may be treated as static by the caller.

 **

 ** The declaration type is the exact datatype definition extracted from the

 ** original CREATE TABLE statement if the expression is a column. The

 ** declaration type for a ROWID field is INTEGER. Exactly when an expression

 ** is considered a column can be complex in the presence of subqueries. The

 ** result-set expression in all of the following SELECT statements is 

 ** considered a column by this function.

 **

 **   SELECT col FROM tbl;

 **   SELECT (SELECT col FROM tbl;

 **   SELECT (SELECT col FROM tbl);

 **   SELECT abc FROM (SELECT col AS abc FROM tbl);

 ** 

 ** The declaration type for any expression other than a column is NULL.

 */

 static const char *columnType(

   NameContext *pNC, 

   Expr *pExpr,

   const char **pzOriginDb,

   const char **pzOriginTab,

   const char **pzOriginCol

 ){

   char const *zType = 0;

   char const *zOriginDb = 0;

   char const *zOriginTab = 0;

   char const *zOriginCol = 0;

   int j;

   if( pExpr==0 || pNC->pSrcList==0 ) return 0;

   switch( pExpr->op ){

     case TK_AGG_COLUMN:

     case TK_COLUMN: {

       /* The expression is a column. Locate the table the column is being

       ** extracted from in NameContext.pSrcList. This table may be real

       ** database table or a subquery.

       */

       Table *pTab = 0;            /* Table structure column is extracted from */

       Select *pS = 0;             /* Select the column is extracted from */

       int iCol = pExpr->iColumn;  /* Index of column in pTab */

       while( pNC && !pTab ){

         SrcList *pTabList = pNC->pSrcList;

         for(j=0;j<pTabList->nSrc && pTabList->a[j].iCursor!=pExpr->iTable;j++);

         if( j<pTabList->nSrc ){

           pTab = pTabList->a[j].pTab;