Back to index

lightning-sunbird  0.9+nobinonly
select.c
Go to the documentation of this file.
00001 /*
00002 ** 2001 September 15
00003 **
00004 ** The author disclaims copyright to this source code.  In place of
00005 ** a legal notice, here is a blessing:
00006 **
00007 **    May you do good and not evil.
00008 **    May you find forgiveness for yourself and forgive others.
00009 **    May you share freely, never taking more than you give.
00010 **
00011 *************************************************************************
00012 ** This file contains C code routines that are called by the parser
00013 ** to handle SELECT statements in SQLite.
00014 **
00015 ** $Id: select.c,v 1.313 2006/04/26 17:39:34 drh Exp $
00016 */
00017 #include "sqliteInt.h"
00018 
00019 
00020 /*
00021 ** Delete all the content of a Select structure but do not deallocate
00022 ** the select structure itself.
00023 */
00024 static void clearSelect(Select *p){
00025   sqlite3ExprListDelete(p->pEList);
00026   sqlite3SrcListDelete(p->pSrc);
00027   sqlite3ExprDelete(p->pWhere);
00028   sqlite3ExprListDelete(p->pGroupBy);
00029   sqlite3ExprDelete(p->pHaving);
00030   sqlite3ExprListDelete(p->pOrderBy);
00031   sqlite3SelectDelete(p->pPrior);
00032   sqlite3ExprDelete(p->pLimit);
00033   sqlite3ExprDelete(p->pOffset);
00034 }
00035 
00036 
00037 /*
00038 ** Allocate a new Select structure and return a pointer to that
00039 ** structure.
00040 */
00041 Select *sqlite3SelectNew(
00042   ExprList *pEList,     /* which columns to include in the result */
00043   SrcList *pSrc,        /* the FROM clause -- which tables to scan */
00044   Expr *pWhere,         /* the WHERE clause */
00045   ExprList *pGroupBy,   /* the GROUP BY clause */
00046   Expr *pHaving,        /* the HAVING clause */
00047   ExprList *pOrderBy,   /* the ORDER BY clause */
00048   int isDistinct,       /* true if the DISTINCT keyword is present */
00049   Expr *pLimit,         /* LIMIT value.  NULL means not used */
00050   Expr *pOffset         /* OFFSET value.  NULL means no offset */
00051 ){
00052   Select *pNew;
00053   Select standin;
00054   pNew = sqliteMalloc( sizeof(*pNew) );
00055   assert( !pOffset || pLimit );   /* Can't have OFFSET without LIMIT. */
00056   if( pNew==0 ){
00057     pNew = &standin;
00058     memset(pNew, 0, sizeof(*pNew));
00059   }
00060   if( pEList==0 ){
00061     pEList = sqlite3ExprListAppend(0, sqlite3Expr(TK_ALL,0,0,0), 0);
00062   }
00063   pNew->pEList = pEList;
00064   pNew->pSrc = pSrc;
00065   pNew->pWhere = pWhere;
00066   pNew->pGroupBy = pGroupBy;
00067   pNew->pHaving = pHaving;
00068   pNew->pOrderBy = pOrderBy;
00069   pNew->isDistinct = isDistinct;
00070   pNew->op = TK_SELECT;
00071   pNew->pLimit = pLimit;
00072   pNew->pOffset = pOffset;
00073   pNew->iLimit = -1;
00074   pNew->iOffset = -1;
00075   pNew->addrOpenVirt[0] = -1;
00076   pNew->addrOpenVirt[1] = -1;
00077   pNew->addrOpenVirt[2] = -1;
00078   if( pNew==&standin) {
00079     clearSelect(pNew);
00080     pNew = 0;
00081   }
00082   return pNew;
00083 }
00084 
00085 /*
00086 ** Delete the given Select structure and all of its substructures.
00087 */
00088 void sqlite3SelectDelete(Select *p){
00089   if( p ){
00090     clearSelect(p);
00091     sqliteFree(p);
00092   }
00093 }
00094 
00095 /*
00096 ** Given 1 to 3 identifiers preceeding the JOIN keyword, determine the
00097 ** type of join.  Return an integer constant that expresses that type
00098 ** in terms of the following bit values:
00099 **
00100 **     JT_INNER
00101 **     JT_CROSS
00102 **     JT_OUTER
00103 **     JT_NATURAL
00104 **     JT_LEFT
00105 **     JT_RIGHT
00106 **
00107 ** A full outer join is the combination of JT_LEFT and JT_RIGHT.
00108 **
00109 ** If an illegal or unsupported join type is seen, then still return
00110 ** a join type, but put an error in the pParse structure.
00111 */
00112 int sqlite3JoinType(Parse *pParse, Token *pA, Token *pB, Token *pC){
00113   int jointype = 0;
00114   Token *apAll[3];
00115   Token *p;
00116   static const struct {
00117     const char zKeyword[8];
00118     u8 nChar;
00119     u8 code;
00120   } keywords[] = {
00121     { "natural", 7, JT_NATURAL },
00122     { "left",    4, JT_LEFT|JT_OUTER },
00123     { "right",   5, JT_RIGHT|JT_OUTER },
00124     { "full",    4, JT_LEFT|JT_RIGHT|JT_OUTER },
00125     { "outer",   5, JT_OUTER },
00126     { "inner",   5, JT_INNER },
00127     { "cross",   5, JT_INNER|JT_CROSS },
00128   };
00129   int i, j;
00130   apAll[0] = pA;
00131   apAll[1] = pB;
00132   apAll[2] = pC;
00133   for(i=0; i<3 && apAll[i]; i++){
00134     p = apAll[i];
00135     for(j=0; j<sizeof(keywords)/sizeof(keywords[0]); j++){
00136       if( p->n==keywords[j].nChar 
00137           && sqlite3StrNICmp((char*)p->z, keywords[j].zKeyword, p->n)==0 ){
00138         jointype |= keywords[j].code;
00139         break;
00140       }
00141     }
00142     if( j>=sizeof(keywords)/sizeof(keywords[0]) ){
00143       jointype |= JT_ERROR;
00144       break;
00145     }
00146   }
00147   if(
00148      (jointype & (JT_INNER|JT_OUTER))==(JT_INNER|JT_OUTER) ||
00149      (jointype & JT_ERROR)!=0
00150   ){
00151     const char *zSp1 = " ";
00152     const char *zSp2 = " ";
00153     if( pB==0 ){ zSp1++; }
00154     if( pC==0 ){ zSp2++; }
00155     sqlite3ErrorMsg(pParse, "unknown or unsupported join type: "
00156        "%T%s%T%s%T", pA, zSp1, pB, zSp2, pC);
00157     jointype = JT_INNER;
00158   }else if( jointype & JT_RIGHT ){
00159     sqlite3ErrorMsg(pParse, 
00160       "RIGHT and FULL OUTER JOINs are not currently supported");
00161     jointype = JT_INNER;
00162   }
00163   return jointype;
00164 }
00165 
00166 /*
00167 ** Return the index of a column in a table.  Return -1 if the column
00168 ** is not contained in the table.
00169 */
00170 static int columnIndex(Table *pTab, const char *zCol){
00171   int i;
00172   for(i=0; i<pTab->nCol; i++){
00173     if( sqlite3StrICmp(pTab->aCol[i].zName, zCol)==0 ) return i;
00174   }
00175   return -1;
00176 }
00177 
00178 /*
00179 ** Set the value of a token to a '\000'-terminated string.
00180 */
00181 static void setToken(Token *p, const char *z){
00182   p->z = (u8*)z;
00183   p->n = z ? strlen(z) : 0;
00184   p->dyn = 0;
00185 }
00186 
00187 /*
00188 ** Create an expression node for an identifier with the name of zName
00189 */
00190 static Expr *createIdExpr(const char *zName){
00191   Token dummy;
00192   setToken(&dummy, zName);
00193   return sqlite3Expr(TK_ID, 0, 0, &dummy);
00194 }
00195 
00196 
00197 /*
00198 ** Add a term to the WHERE expression in *ppExpr that requires the
00199 ** zCol column to be equal in the two tables pTab1 and pTab2.
00200 */
00201 static void addWhereTerm(
00202   const char *zCol,        /* Name of the column */
00203   const Table *pTab1,      /* First table */
00204   const char *zAlias1,     /* Alias for first table.  May be NULL */
00205   const Table *pTab2,      /* Second table */
00206   const char *zAlias2,     /* Alias for second table.  May be NULL */
00207   int iRightJoinTable,     /* VDBE cursor for the right table */
00208   Expr **ppExpr            /* Add the equality term to this expression */
00209 ){
00210   Expr *pE1a, *pE1b, *pE1c;
00211   Expr *pE2a, *pE2b, *pE2c;
00212   Expr *pE;
00213 
00214   pE1a = createIdExpr(zCol);
00215   pE2a = createIdExpr(zCol);
00216   if( zAlias1==0 ){
00217     zAlias1 = pTab1->zName;
00218   }
00219   pE1b = createIdExpr(zAlias1);
00220   if( zAlias2==0 ){
00221     zAlias2 = pTab2->zName;
00222   }
00223   pE2b = createIdExpr(zAlias2);
00224   pE1c = sqlite3Expr(TK_DOT, pE1b, pE1a, 0);
00225   pE2c = sqlite3Expr(TK_DOT, pE2b, pE2a, 0);
00226   pE = sqlite3Expr(TK_EQ, pE1c, pE2c, 0);
00227   ExprSetProperty(pE, EP_FromJoin);
00228   pE->iRightJoinTable = iRightJoinTable;
00229   *ppExpr = sqlite3ExprAnd(*ppExpr, pE);
00230 }
00231 
00232 /*
00233 ** Set the EP_FromJoin property on all terms of the given expression.
00234 ** And set the Expr.iRightJoinTable to iTable for every term in the
00235 ** expression.
00236 **
00237 ** The EP_FromJoin property is used on terms of an expression to tell
00238 ** the LEFT OUTER JOIN processing logic that this term is part of the
00239 ** join restriction specified in the ON or USING clause and not a part
00240 ** of the more general WHERE clause.  These terms are moved over to the
00241 ** WHERE clause during join processing but we need to remember that they
00242 ** originated in the ON or USING clause.
00243 **
00244 ** The Expr.iRightJoinTable tells the WHERE clause processing that the
00245 ** expression depends on table iRightJoinTable even if that table is not
00246 ** explicitly mentioned in the expression.  That information is needed
00247 ** for cases like this:
00248 **
00249 **    SELECT * FROM t1 LEFT JOIN t2 ON t1.a=t2.b AND t1.x=5
00250 **
00251 ** The where clause needs to defer the handling of the t1.x=5
00252 ** term until after the t2 loop of the join.  In that way, a
00253 ** NULL t2 row will be inserted whenever t1.x!=5.  If we do not
00254 ** defer the handling of t1.x=5, it will be processed immediately
00255 ** after the t1 loop and rows with t1.x!=5 will never appear in
00256 ** the output, which is incorrect.
00257 */
00258 static void setJoinExpr(Expr *p, int iTable){
00259   while( p ){
00260     ExprSetProperty(p, EP_FromJoin);
00261     p->iRightJoinTable = iTable;
00262     setJoinExpr(p->pLeft, iTable);
00263     p = p->pRight;
00264   } 
00265 }
00266 
00267 /*
00268 ** This routine processes the join information for a SELECT statement.
00269 ** ON and USING clauses are converted into extra terms of the WHERE clause.
00270 ** NATURAL joins also create extra WHERE clause terms.
00271 **
00272 ** The terms of a FROM clause are contained in the Select.pSrc structure.
00273 ** The left most table is the first entry in Select.pSrc.  The right-most
00274 ** table is the last entry.  The join operator is held in the entry to
00275 ** the left.  Thus entry 0 contains the join operator for the join between
00276 ** entries 0 and 1.  Any ON or USING clauses associated with the join are
00277 ** also attached to the left entry.
00278 **
00279 ** This routine returns the number of errors encountered.
00280 */
00281 static int sqliteProcessJoin(Parse *pParse, Select *p){
00282   SrcList *pSrc;                  /* All tables in the FROM clause */
00283   int i, j;                       /* Loop counters */
00284   struct SrcList_item *pLeft;     /* Left table being joined */
00285   struct SrcList_item *pRight;    /* Right table being joined */
00286 
00287   pSrc = p->pSrc;
00288   pLeft = &pSrc->a[0];
00289   pRight = &pLeft[1];
00290   for(i=0; i<pSrc->nSrc-1; i++, pRight++, pLeft++){
00291     Table *pLeftTab = pLeft->pTab;
00292     Table *pRightTab = pRight->pTab;
00293 
00294     if( pLeftTab==0 || pRightTab==0 ) continue;
00295 
00296     /* When the NATURAL keyword is present, add WHERE clause terms for
00297     ** every column that the two tables have in common.
00298     */
00299     if( pLeft->jointype & JT_NATURAL ){
00300       if( pLeft->pOn || pLeft->pUsing ){
00301         sqlite3ErrorMsg(pParse, "a NATURAL join may not have "
00302            "an ON or USING clause", 0);
00303         return 1;
00304       }
00305       for(j=0; j<pLeftTab->nCol; j++){
00306         char *zName = pLeftTab->aCol[j].zName;
00307         if( columnIndex(pRightTab, zName)>=0 ){
00308           addWhereTerm(zName, pLeftTab, pLeft->zAlias, 
00309                               pRightTab, pRight->zAlias,
00310                               pRight->iCursor, &p->pWhere);
00311           
00312         }
00313       }
00314     }
00315 
00316     /* Disallow both ON and USING clauses in the same join
00317     */
00318     if( pLeft->pOn && pLeft->pUsing ){
00319       sqlite3ErrorMsg(pParse, "cannot have both ON and USING "
00320         "clauses in the same join");
00321       return 1;
00322     }
00323 
00324     /* Add the ON clause to the end of the WHERE clause, connected by
00325     ** an AND operator.
00326     */
00327     if( pLeft->pOn ){
00328       setJoinExpr(pLeft->pOn, pRight->iCursor);
00329       p->pWhere = sqlite3ExprAnd(p->pWhere, pLeft->pOn);
00330       pLeft->pOn = 0;
00331     }
00332 
00333     /* Create extra terms on the WHERE clause for each column named
00334     ** in the USING clause.  Example: If the two tables to be joined are 
00335     ** A and B and the USING clause names X, Y, and Z, then add this
00336     ** to the WHERE clause:    A.X=B.X AND A.Y=B.Y AND A.Z=B.Z
00337     ** Report an error if any column mentioned in the USING clause is
00338     ** not contained in both tables to be joined.
00339     */
00340     if( pLeft->pUsing ){
00341       IdList *pList = pLeft->pUsing;
00342       for(j=0; j<pList->nId; j++){
00343         char *zName = pList->a[j].zName;
00344         if( columnIndex(pLeftTab, zName)<0 || columnIndex(pRightTab, zName)<0 ){
00345           sqlite3ErrorMsg(pParse, "cannot join using column %s - column "
00346             "not present in both tables", zName);
00347           return 1;
00348         }
00349         addWhereTerm(zName, pLeftTab, pLeft->zAlias, 
00350                             pRightTab, pRight->zAlias,
00351                             pRight->iCursor, &p->pWhere);
00352       }
00353     }
00354   }
00355   return 0;
00356 }
00357 
00358 /*
00359 ** Insert code into "v" that will push the record on the top of the
00360 ** stack into the sorter.
00361 */
00362 static void pushOntoSorter(
00363   Parse *pParse,         /* Parser context */
00364   ExprList *pOrderBy,    /* The ORDER BY clause */
00365   Select *pSelect        /* The whole SELECT statement */
00366 ){
00367   Vdbe *v = pParse->pVdbe;
00368   sqlite3ExprCodeExprList(pParse, pOrderBy);
00369   sqlite3VdbeAddOp(v, OP_Sequence, pOrderBy->iECursor, 0);
00370   sqlite3VdbeAddOp(v, OP_Pull, pOrderBy->nExpr + 1, 0);
00371   sqlite3VdbeAddOp(v, OP_MakeRecord, pOrderBy->nExpr + 2, 0);
00372   sqlite3VdbeAddOp(v, OP_IdxInsert, pOrderBy->iECursor, 0);
00373   if( pSelect->iLimit>=0 ){
00374     int addr1, addr2;
00375     addr1 = sqlite3VdbeAddOp(v, OP_IfMemZero, pSelect->iLimit+1, 0);
00376     sqlite3VdbeAddOp(v, OP_MemIncr, -1, pSelect->iLimit+1);
00377     addr2 = sqlite3VdbeAddOp(v, OP_Goto, 0, 0);
00378     sqlite3VdbeJumpHere(v, addr1);
00379     sqlite3VdbeAddOp(v, OP_Last, pOrderBy->iECursor, 0);
00380     sqlite3VdbeAddOp(v, OP_Delete, pOrderBy->iECursor, 0);
00381     sqlite3VdbeJumpHere(v, addr2);
00382     pSelect->iLimit = -1;
00383   }
00384 }
00385 
00386 /*
00387 ** Add code to implement the OFFSET
00388 */
00389 static void codeOffset(
00390   Vdbe *v,          /* Generate code into this VM */
00391   Select *p,        /* The SELECT statement being coded */
00392   int iContinue,    /* Jump here to skip the current record */
00393   int nPop          /* Number of times to pop stack when jumping */
00394 ){
00395   if( p->iOffset>=0 && iContinue!=0 ){
00396     int addr;
00397     sqlite3VdbeAddOp(v, OP_MemIncr, -1, p->iOffset);
00398     addr = sqlite3VdbeAddOp(v, OP_IfMemNeg, p->iOffset, 0);
00399     if( nPop>0 ){
00400       sqlite3VdbeAddOp(v, OP_Pop, nPop, 0);
00401     }
00402     sqlite3VdbeAddOp(v, OP_Goto, 0, iContinue);
00403     VdbeComment((v, "# skip OFFSET records"));
00404     sqlite3VdbeJumpHere(v, addr);
00405   }
00406 }
00407 
00408 /*
00409 ** Add code that will check to make sure the top N elements of the
00410 ** stack are distinct.  iTab is a sorting index that holds previously
00411 ** seen combinations of the N values.  A new entry is made in iTab
00412 ** if the current N values are new.
00413 **
00414 ** A jump to addrRepeat is made and the N+1 values are popped from the
00415 ** stack if the top N elements are not distinct.
00416 */
00417 static void codeDistinct(
00418   Vdbe *v,           /* Generate code into this VM */
00419   int iTab,          /* A sorting index used to test for distinctness */
00420   int addrRepeat,    /* Jump to here if not distinct */
00421   int N              /* The top N elements of the stack must be distinct */
00422 ){
00423   sqlite3VdbeAddOp(v, OP_MakeRecord, -N, 0);
00424   sqlite3VdbeAddOp(v, OP_Distinct, iTab, sqlite3VdbeCurrentAddr(v)+3);
00425   sqlite3VdbeAddOp(v, OP_Pop, N+1, 0);
00426   sqlite3VdbeAddOp(v, OP_Goto, 0, addrRepeat);
00427   VdbeComment((v, "# skip indistinct records"));
00428   sqlite3VdbeAddOp(v, OP_IdxInsert, iTab, 0);
00429 }
00430 
00431 
00432 /*
00433 ** This routine generates the code for the inside of the inner loop
00434 ** of a SELECT.
00435 **
00436 ** If srcTab and nColumn are both zero, then the pEList expressions
00437 ** are evaluated in order to get the data for this row.  If nColumn>0
00438 ** then data is pulled from srcTab and pEList is used only to get the
00439 ** datatypes for each column.
00440 */
00441 static int selectInnerLoop(
00442   Parse *pParse,          /* The parser context */
00443   Select *p,              /* The complete select statement being coded */
00444   ExprList *pEList,       /* List of values being extracted */
00445   int srcTab,             /* Pull data from this table */
00446   int nColumn,            /* Number of columns in the source table */
00447   ExprList *pOrderBy,     /* If not NULL, sort results using this key */
00448   int distinct,           /* If >=0, make sure results are distinct */
00449   int eDest,              /* How to dispose of the results */
00450   int iParm,              /* An argument to the disposal method */
00451   int iContinue,          /* Jump here to continue with next row */
00452   int iBreak,             /* Jump here to break out of the inner loop */
00453   char *aff               /* affinity string if eDest is SRT_Union */
00454 ){
00455   Vdbe *v = pParse->pVdbe;
00456   int i;
00457   int hasDistinct;        /* True if the DISTINCT keyword is present */
00458 
00459   if( v==0 ) return 0;
00460   assert( pEList!=0 );
00461 
00462   /* If there was a LIMIT clause on the SELECT statement, then do the check
00463   ** to see if this row should be output.
00464   */
00465   hasDistinct = distinct>=0 && pEList->nExpr>0;
00466   if( pOrderBy==0 && !hasDistinct ){
00467     codeOffset(v, p, iContinue, 0);
00468   }
00469 
00470   /* Pull the requested columns.
00471   */
00472   if( nColumn>0 ){
00473     for(i=0; i<nColumn; i++){
00474       sqlite3VdbeAddOp(v, OP_Column, srcTab, i);
00475     }
00476   }else{
00477     nColumn = pEList->nExpr;
00478     sqlite3ExprCodeExprList(pParse, pEList);
00479   }
00480 
00481   /* If the DISTINCT keyword was present on the SELECT statement
00482   ** and this row has been seen before, then do not make this row
00483   ** part of the result.
00484   */
00485   if( hasDistinct ){
00486     assert( pEList!=0 );
00487     assert( pEList->nExpr==nColumn );
00488     codeDistinct(v, distinct, iContinue, nColumn);
00489     if( pOrderBy==0 ){
00490       codeOffset(v, p, iContinue, nColumn);
00491     }
00492   }
00493 
00494   switch( eDest ){
00495     /* In this mode, write each query result to the key of the temporary
00496     ** table iParm.
00497     */
00498 #ifndef SQLITE_OMIT_COMPOUND_SELECT
00499     case SRT_Union: {
00500       sqlite3VdbeAddOp(v, OP_MakeRecord, nColumn, 0);
00501       if( aff ){
00502         sqlite3VdbeChangeP3(v, -1, aff, P3_STATIC);
00503       }
00504       sqlite3VdbeAddOp(v, OP_IdxInsert, iParm, 0);
00505       break;
00506     }
00507 
00508     /* Construct a record from the query result, but instead of
00509     ** saving that record, use it as a key to delete elements from
00510     ** the temporary table iParm.
00511     */
00512     case SRT_Except: {
00513       int addr;
00514       addr = sqlite3VdbeAddOp(v, OP_MakeRecord, nColumn, 0);
00515       sqlite3VdbeChangeP3(v, -1, aff, P3_STATIC);
00516       sqlite3VdbeAddOp(v, OP_NotFound, iParm, addr+3);
00517       sqlite3VdbeAddOp(v, OP_Delete, iParm, 0);
00518       break;
00519     }
00520 #endif
00521 
00522     /* Store the result as data using a unique key.
00523     */
00524     case SRT_Table:
00525     case SRT_VirtualTab: {
00526       sqlite3VdbeAddOp(v, OP_MakeRecord, nColumn, 0);
00527       if( pOrderBy ){
00528         pushOntoSorter(pParse, pOrderBy, p);
00529       }else{
00530         sqlite3VdbeAddOp(v, OP_NewRowid, iParm, 0);
00531         sqlite3VdbeAddOp(v, OP_Pull, 1, 0);
00532         sqlite3VdbeAddOp(v, OP_Insert, iParm, 0);
00533       }
00534       break;
00535     }
00536 
00537 #ifndef SQLITE_OMIT_SUBQUERY
00538     /* If we are creating a set for an "expr IN (SELECT ...)" construct,
00539     ** then there should be a single item on the stack.  Write this
00540     ** item into the set table with bogus data.
00541     */
00542     case SRT_Set: {
00543       int addr1 = sqlite3VdbeCurrentAddr(v);
00544       int addr2;
00545 
00546       assert( nColumn==1 );
00547       sqlite3VdbeAddOp(v, OP_NotNull, -1, addr1+3);
00548       sqlite3VdbeAddOp(v, OP_Pop, 1, 0);
00549       addr2 = sqlite3VdbeAddOp(v, OP_Goto, 0, 0);
00550       if( pOrderBy ){
00551         /* At first glance you would think we could optimize out the
00552         ** ORDER BY in this case since the order of entries in the set
00553         ** does not matter.  But there might be a LIMIT clause, in which
00554         ** case the order does matter */
00555         pushOntoSorter(pParse, pOrderBy, p);
00556       }else{
00557         char affinity = (iParm>>16)&0xFF;
00558         affinity = sqlite3CompareAffinity(pEList->a[0].pExpr, affinity);
00559         sqlite3VdbeOp3(v, OP_MakeRecord, 1, 0, &affinity, 1);
00560         sqlite3VdbeAddOp(v, OP_IdxInsert, (iParm&0x0000FFFF), 0);
00561       }
00562       sqlite3VdbeJumpHere(v, addr2);
00563       break;
00564     }
00565 
00566     /* If any row exist in the result set, record that fact and abort.
00567     */
00568     case SRT_Exists: {
00569       sqlite3VdbeAddOp(v, OP_MemInt, 1, iParm);
00570       sqlite3VdbeAddOp(v, OP_Pop, nColumn, 0);
00571       /* The LIMIT clause will terminate the loop for us */
00572       break;
00573     }
00574 
00575     /* If this is a scalar select that is part of an expression, then
00576     ** store the results in the appropriate memory cell and break out
00577     ** of the scan loop.
00578     */
00579     case SRT_Mem: {
00580       assert( nColumn==1 );
00581       if( pOrderBy ){
00582         pushOntoSorter(pParse, pOrderBy, p);
00583       }else{
00584         sqlite3VdbeAddOp(v, OP_MemStore, iParm, 1);
00585         /* The LIMIT clause will jump out of the loop for us */
00586       }
00587       break;
00588     }
00589 #endif /* #ifndef SQLITE_OMIT_SUBQUERY */
00590 
00591     /* Send the data to the callback function or to a subroutine.  In the
00592     ** case of a subroutine, the subroutine itself is responsible for
00593     ** popping the data from the stack.
00594     */
00595     case SRT_Subroutine:
00596     case SRT_Callback: {
00597       if( pOrderBy ){
00598         sqlite3VdbeAddOp(v, OP_MakeRecord, nColumn, 0);
00599         pushOntoSorter(pParse, pOrderBy, p);
00600       }else if( eDest==SRT_Subroutine ){
00601         sqlite3VdbeAddOp(v, OP_Gosub, 0, iParm);
00602       }else{
00603         sqlite3VdbeAddOp(v, OP_Callback, nColumn, 0);
00604       }
00605       break;
00606     }
00607 
00608 #if !defined(SQLITE_OMIT_TRIGGER)
00609     /* Discard the results.  This is used for SELECT statements inside
00610     ** the body of a TRIGGER.  The purpose of such selects is to call
00611     ** user-defined functions that have side effects.  We do not care
00612     ** about the actual results of the select.
00613     */
00614     default: {
00615       assert( eDest==SRT_Discard );
00616       sqlite3VdbeAddOp(v, OP_Pop, nColumn, 0);
00617       break;
00618     }
00619 #endif
00620   }
00621 
00622   /* Jump to the end of the loop if the LIMIT is reached.
00623   */
00624   if( p->iLimit>=0 && pOrderBy==0 ){
00625     sqlite3VdbeAddOp(v, OP_MemIncr, -1, p->iLimit);
00626     sqlite3VdbeAddOp(v, OP_IfMemZero, p->iLimit, iBreak);
00627   }
00628   return 0;
00629 }
00630 
00631 /*
00632 ** Given an expression list, generate a KeyInfo structure that records
00633 ** the collating sequence for each expression in that expression list.
00634 **
00635 ** If the ExprList is an ORDER BY or GROUP BY clause then the resulting
00636 ** KeyInfo structure is appropriate for initializing a virtual index to
00637 ** implement that clause.  If the ExprList is the result set of a SELECT
00638 ** then the KeyInfo structure is appropriate for initializing a virtual
00639 ** index to implement a DISTINCT test.
00640 **
00641 ** Space to hold the KeyInfo structure is obtain from malloc.  The calling
00642 ** function is responsible for seeing that this structure is eventually
00643 ** freed.  Add the KeyInfo structure to the P3 field of an opcode using
00644 ** P3_KEYINFO_HANDOFF is the usual way of dealing with this.
00645 */
00646 static KeyInfo *keyInfoFromExprList(Parse *pParse, ExprList *pList){
00647   sqlite3 *db = pParse->db;
00648   int nExpr;
00649   KeyInfo *pInfo;
00650   struct ExprList_item *pItem;
00651   int i;
00652 
00653   nExpr = pList->nExpr;
00654   pInfo = sqliteMalloc( sizeof(*pInfo) + nExpr*(sizeof(CollSeq*)+1) );
00655   if( pInfo ){
00656     pInfo->aSortOrder = (u8*)&pInfo->aColl[nExpr];
00657     pInfo->nField = nExpr;
00658     pInfo->enc = ENC(db);
00659     for(i=0, pItem=pList->a; i<nExpr; i++, pItem++){
00660       CollSeq *pColl;
00661       pColl = sqlite3ExprCollSeq(pParse, pItem->pExpr);
00662       if( !pColl ){
00663         pColl = db->pDfltColl;
00664       }
00665       pInfo->aColl[i] = pColl;
00666       pInfo->aSortOrder[i] = pItem->sortOrder;
00667     }
00668   }
00669   return pInfo;
00670 }
00671 
00672 
00673 /*
00674 ** If the inner loop was generated using a non-null pOrderBy argument,
00675 ** then the results were placed in a sorter.  After the loop is terminated
00676 ** we need to run the sorter and output the results.  The following
00677 ** routine generates the code needed to do that.
00678 */
00679 static void generateSortTail(
00680   Parse *pParse,   /* Parsing context */
00681   Select *p,       /* The SELECT statement */
00682   Vdbe *v,         /* Generate code into this VDBE */
00683   int nColumn,     /* Number of columns of data */
00684   int eDest,       /* Write the sorted results here */
00685   int iParm        /* Optional parameter associated with eDest */
00686 ){
00687   int brk = sqlite3VdbeMakeLabel(v);
00688   int cont = sqlite3VdbeMakeLabel(v);
00689   int addr;
00690   int iTab;
00691   int pseudoTab;
00692   ExprList *pOrderBy = p->pOrderBy;
00693 
00694   iTab = pOrderBy->iECursor;
00695   if( eDest==SRT_Callback || eDest==SRT_Subroutine ){
00696     pseudoTab = pParse->nTab++;
00697     sqlite3VdbeAddOp(v, OP_OpenPseudo, pseudoTab, 0);
00698     sqlite3VdbeAddOp(v, OP_SetNumColumns, pseudoTab, nColumn);
00699   }
00700   addr = 1 + sqlite3VdbeAddOp(v, OP_Sort, iTab, brk);
00701   codeOffset(v, p, cont, 0);
00702   if( eDest==SRT_Callback || eDest==SRT_Subroutine ){
00703     sqlite3VdbeAddOp(v, OP_Integer, 1, 0);
00704   }
00705   sqlite3VdbeAddOp(v, OP_Column, iTab, pOrderBy->nExpr + 1);
00706   switch( eDest ){
00707     case SRT_Table:
00708     case SRT_VirtualTab: {
00709       sqlite3VdbeAddOp(v, OP_NewRowid, iParm, 0);
00710       sqlite3VdbeAddOp(v, OP_Pull, 1, 0);
00711       sqlite3VdbeAddOp(v, OP_Insert, iParm, 0);
00712       break;
00713     }
00714 #ifndef SQLITE_OMIT_SUBQUERY
00715     case SRT_Set: {
00716       assert( nColumn==1 );
00717       sqlite3VdbeAddOp(v, OP_NotNull, -1, sqlite3VdbeCurrentAddr(v)+3);
00718       sqlite3VdbeAddOp(v, OP_Pop, 1, 0);
00719       sqlite3VdbeAddOp(v, OP_Goto, 0, sqlite3VdbeCurrentAddr(v)+3);
00720       sqlite3VdbeOp3(v, OP_MakeRecord, 1, 0, "c", P3_STATIC);
00721       sqlite3VdbeAddOp(v, OP_IdxInsert, (iParm&0x0000FFFF), 0);
00722       break;
00723     }
00724     case SRT_Mem: {
00725       assert( nColumn==1 );
00726       sqlite3VdbeAddOp(v, OP_MemStore, iParm, 1);
00727       /* The LIMIT clause will terminate the loop for us */
00728       break;
00729     }
00730 #endif
00731     case SRT_Callback:
00732     case SRT_Subroutine: {
00733       int i;
00734       sqlite3VdbeAddOp(v, OP_Insert, pseudoTab, 0);
00735       for(i=0; i<nColumn; i++){
00736         sqlite3VdbeAddOp(v, OP_Column, pseudoTab, i);
00737       }
00738       if( eDest==SRT_Callback ){
00739         sqlite3VdbeAddOp(v, OP_Callback, nColumn, 0);
00740       }else{
00741         sqlite3VdbeAddOp(v, OP_Gosub, 0, iParm);
00742       }
00743       break;
00744     }
00745     default: {
00746       /* Do nothing */
00747       break;
00748     }
00749   }
00750 
00751   /* Jump to the end of the loop when the LIMIT is reached
00752   */
00753   if( p->iLimit>=0 ){
00754     sqlite3VdbeAddOp(v, OP_MemIncr, -1, p->iLimit);
00755     sqlite3VdbeAddOp(v, OP_IfMemZero, p->iLimit, brk);
00756   }
00757 
00758   /* The bottom of the loop
00759   */
00760   sqlite3VdbeResolveLabel(v, cont);
00761   sqlite3VdbeAddOp(v, OP_Next, iTab, addr);
00762   sqlite3VdbeResolveLabel(v, brk);
00763   if( eDest==SRT_Callback || eDest==SRT_Subroutine ){
00764     sqlite3VdbeAddOp(v, OP_Close, pseudoTab, 0);
00765   }
00766 
00767 }
00768 
00769 /*
00770 ** Return a pointer to a string containing the 'declaration type' of the
00771 ** expression pExpr. The string may be treated as static by the caller.
00772 **
00773 ** The declaration type is the exact datatype definition extracted from the
00774 ** original CREATE TABLE statement if the expression is a column. The
00775 ** declaration type for a ROWID field is INTEGER. Exactly when an expression
00776 ** is considered a column can be complex in the presence of subqueries. The
00777 ** result-set expression in all of the following SELECT statements is 
00778 ** considered a column by this function.
00779 **
00780 **   SELECT col FROM tbl;
00781 **   SELECT (SELECT col FROM tbl;
00782 **   SELECT (SELECT col FROM tbl);
00783 **   SELECT abc FROM (SELECT col AS abc FROM tbl);
00784 ** 
00785 ** The declaration type for any expression other than a column is NULL.
00786 */
00787 static const char *columnType(
00788   NameContext *pNC, 
00789   Expr *pExpr,
00790   const char **pzOriginDb,
00791   const char **pzOriginTab,
00792   const char **pzOriginCol
00793 ){
00794   char const *zType = 0;
00795   char const *zOriginDb = 0;
00796   char const *zOriginTab = 0;
00797   char const *zOriginCol = 0;
00798   int j;
00799   if( pExpr==0 || pNC->pSrcList==0 ) return 0;
00800 
00801   /* The TK_AS operator can only occur in ORDER BY, GROUP BY, HAVING,
00802   ** and LIMIT clauses.  But pExpr originates in the result set of a
00803   ** SELECT.  So pExpr can never contain an AS operator.
00804   */
00805   assert( pExpr->op!=TK_AS );
00806 
00807   switch( pExpr->op ){
00808     case TK_AGG_COLUMN:
00809     case TK_COLUMN: {
00810       /* The expression is a column. Locate the table the column is being
00811       ** extracted from in NameContext.pSrcList. This table may be real
00812       ** database table or a subquery.
00813       */
00814       Table *pTab = 0;            /* Table structure column is extracted from */
00815       Select *pS = 0;             /* Select the column is extracted from */
00816       int iCol = pExpr->iColumn;  /* Index of column in pTab */
00817       while( pNC && !pTab ){
00818         SrcList *pTabList = pNC->pSrcList;
00819         for(j=0;j<pTabList->nSrc && pTabList->a[j].iCursor!=pExpr->iTable;j++);
00820         if( j<pTabList->nSrc ){
00821           pTab = pTabList->a[j].pTab;
00822           pS = pTabList->a[j].pSelect;
00823         }else{
00824           pNC = pNC->pNext;
00825         }
00826       }
00827 
00828       if( pTab==0 ){
00829         /* FIX ME:
00830         ** This can occurs if you have something like "SELECT new.x;" inside
00831         ** a trigger.  In other words, if you reference the special "new"
00832         ** table in the result set of a select.  We do not have a good way
00833         ** to find the actual table type, so call it "TEXT".  This is really
00834         ** something of a bug, but I do not know how to fix it.
00835         **
00836         ** This code does not produce the correct answer - it just prevents
00837         ** a segfault.  See ticket #1229.
00838         */
00839         zType = "TEXT";
00840         break;
00841       }
00842 
00843       assert( pTab );
00844 #ifndef SQLITE_OMIT_SUBQUERY
00845       if( pS ){
00846         /* The "table" is actually a sub-select or a view in the FROM clause
00847         ** of the SELECT statement. Return the declaration type and origin
00848         ** data for the result-set column of the sub-select.
00849         */
00850         if( iCol>=0 && iCol<pS->pEList->nExpr ){
00851           /* If iCol is less than zero, then the expression requests the
00852           ** rowid of the sub-select or view. This expression is legal (see 
00853           ** test case misc2.2.2) - it always evaluates to NULL.
00854           */
00855           NameContext sNC;
00856           Expr *p = pS->pEList->a[iCol].pExpr;
00857           sNC.pSrcList = pS->pSrc;
00858           sNC.pNext = 0;
00859           sNC.pParse = pNC->pParse;
00860           zType = columnType(&sNC, p, &zOriginDb, &zOriginTab, &zOriginCol); 
00861         }
00862       }else
00863 #endif
00864       if( pTab->pSchema ){
00865         /* A real table */
00866         assert( !pS );
00867         if( iCol<0 ) iCol = pTab->iPKey;
00868         assert( iCol==-1 || (iCol>=0 && iCol<pTab->nCol) );
00869         if( iCol<0 ){
00870           zType = "INTEGER";
00871           zOriginCol = "rowid";
00872         }else{
00873           zType = pTab->aCol[iCol].zType;
00874           zOriginCol = pTab->aCol[iCol].zName;
00875         }
00876         zOriginTab = pTab->zName;
00877         if( pNC->pParse ){
00878           int iDb = sqlite3SchemaToIndex(pNC->pParse->db, pTab->pSchema);
00879           zOriginDb = pNC->pParse->db->aDb[iDb].zName;
00880         }
00881       }
00882       break;
00883     }
00884 #ifndef SQLITE_OMIT_SUBQUERY
00885     case TK_SELECT: {
00886       /* The expression is a sub-select. Return the declaration type and
00887       ** origin info for the single column in the result set of the SELECT
00888       ** statement.
00889       */
00890       NameContext sNC;
00891       Select *pS = pExpr->pSelect;
00892       Expr *p = pS->pEList->a[0].pExpr;
00893       sNC.pSrcList = pS->pSrc;
00894       sNC.pNext = pNC;
00895       sNC.pParse = pNC->pParse;
00896       zType = columnType(&sNC, p, &zOriginDb, &zOriginTab, &zOriginCol); 
00897       break;
00898     }
00899 #endif
00900   }
00901   
00902   if( pzOriginDb ){
00903     assert( pzOriginTab && pzOriginCol );
00904     *pzOriginDb = zOriginDb;
00905     *pzOriginTab = zOriginTab;
00906     *pzOriginCol = zOriginCol;
00907   }
00908   return zType;
00909 }
00910 
00911 /*
00912 ** Generate code that will tell the VDBE the declaration types of columns
00913 ** in the result set.
00914 */
00915 static void generateColumnTypes(
00916   Parse *pParse,      /* Parser context */
00917   SrcList *pTabList,  /* List of tables */
00918   ExprList *pEList    /* Expressions defining the result set */
00919 ){
00920   Vdbe *v = pParse->pVdbe;
00921   int i;
00922   NameContext sNC;
00923   sNC.pSrcList = pTabList;
00924   sNC.pParse = pParse;
00925   for(i=0; i<pEList->nExpr; i++){
00926     Expr *p = pEList->a[i].pExpr;
00927     const char *zOrigDb = 0;
00928     const char *zOrigTab = 0;
00929     const char *zOrigCol = 0;
00930     const char *zType = columnType(&sNC, p, &zOrigDb, &zOrigTab, &zOrigCol);
00931 
00932     /* The vdbe must make it's own copy of the column-type and other 
00933     ** column specific strings, in case the schema is reset before this
00934     ** virtual machine is deleted.
00935     */
00936     sqlite3VdbeSetColName(v, i, COLNAME_DECLTYPE, zType, P3_TRANSIENT);
00937     sqlite3VdbeSetColName(v, i, COLNAME_DATABASE, zOrigDb, P3_TRANSIENT);
00938     sqlite3VdbeSetColName(v, i, COLNAME_TABLE, zOrigTab, P3_TRANSIENT);
00939     sqlite3VdbeSetColName(v, i, COLNAME_COLUMN, zOrigCol, P3_TRANSIENT);
00940   }
00941 }
00942 
00943 /*
00944 ** Generate code that will tell the VDBE the names of columns
00945 ** in the result set.  This information is used to provide the
00946 ** azCol[] values in the callback.
00947 */
00948 static void generateColumnNames(
00949   Parse *pParse,      /* Parser context */
00950   SrcList *pTabList,  /* List of tables */
00951   ExprList *pEList    /* Expressions defining the result set */
00952 ){
00953   Vdbe *v = pParse->pVdbe;
00954   int i, j;
00955   sqlite3 *db = pParse->db;
00956   int fullNames, shortNames;
00957 
00958 #ifndef SQLITE_OMIT_EXPLAIN
00959   /* If this is an EXPLAIN, skip this step */
00960   if( pParse->explain ){
00961     return;
00962   }
00963 #endif
00964 
00965   assert( v!=0 );
00966   if( pParse->colNamesSet || v==0 || sqlite3MallocFailed() ) return;
00967   pParse->colNamesSet = 1;
00968   fullNames = (db->flags & SQLITE_FullColNames)!=0;
00969   shortNames = (db->flags & SQLITE_ShortColNames)!=0;
00970   sqlite3VdbeSetNumCols(v, pEList->nExpr);
00971   for(i=0; i<pEList->nExpr; i++){
00972     Expr *p;
00973     p = pEList->a[i].pExpr;
00974     if( p==0 ) continue;
00975     if( pEList->a[i].zName ){
00976       char *zName = pEList->a[i].zName;
00977       sqlite3VdbeSetColName(v, i, COLNAME_NAME, zName, strlen(zName));
00978       continue;
00979     }
00980     if( p->op==TK_COLUMN && pTabList ){
00981       Table *pTab;
00982       char *zCol;
00983       int iCol = p->iColumn;
00984       for(j=0; j<pTabList->nSrc && pTabList->a[j].iCursor!=p->iTable; j++){}
00985       assert( j<pTabList->nSrc );
00986       pTab = pTabList->a[j].pTab;
00987       if( iCol<0 ) iCol = pTab->iPKey;
00988       assert( iCol==-1 || (iCol>=0 && iCol<pTab->nCol) );
00989       if( iCol<0 ){
00990         zCol = "rowid";
00991       }else{
00992         zCol = pTab->aCol[iCol].zName;
00993       }
00994       if( !shortNames && !fullNames && p->span.z && p->span.z[0] ){
00995         sqlite3VdbeSetColName(v, i, COLNAME_NAME, (char*)p->span.z, p->span.n);
00996       }else if( fullNames || (!shortNames && pTabList->nSrc>1) ){
00997         char *zName = 0;
00998         char *zTab;
00999  
01000         zTab = pTabList->a[j].zAlias;
01001         if( fullNames || zTab==0 ) zTab = pTab->zName;
01002         sqlite3SetString(&zName, zTab, ".", zCol, (char*)0);
01003         sqlite3VdbeSetColName(v, i, COLNAME_NAME, zName, P3_DYNAMIC);
01004       }else{
01005         sqlite3VdbeSetColName(v, i, COLNAME_NAME, zCol, strlen(zCol));
01006       }
01007     }else if( p->span.z && p->span.z[0] ){
01008       sqlite3VdbeSetColName(v, i, COLNAME_NAME, (char*)p->span.z, p->span.n);
01009       /* sqlite3VdbeCompressSpace(v, addr); */
01010     }else{
01011       char zName[30];
01012       assert( p->op!=TK_COLUMN || pTabList==0 );
01013       sprintf(zName, "column%d", i+1);
01014       sqlite3VdbeSetColName(v, i, COLNAME_NAME, zName, 0);
01015     }
01016   }
01017   generateColumnTypes(pParse, pTabList, pEList);
01018 }
01019 
01020 #ifndef SQLITE_OMIT_COMPOUND_SELECT
01021 /*
01022 ** Name of the connection operator, used for error messages.
01023 */
01024 static const char *selectOpName(int id){
01025   char *z;
01026   switch( id ){
01027     case TK_ALL:       z = "UNION ALL";   break;
01028     case TK_INTERSECT: z = "INTERSECT";   break;
01029     case TK_EXCEPT:    z = "EXCEPT";      break;
01030     default:           z = "UNION";       break;
01031   }
01032   return z;
01033 }
01034 #endif /* SQLITE_OMIT_COMPOUND_SELECT */
01035 
01036 /*
01037 ** Forward declaration
01038 */
01039 static int prepSelectStmt(Parse*, Select*);
01040 
01041 /*
01042 ** Given a SELECT statement, generate a Table structure that describes
01043 ** the result set of that SELECT.
01044 */
01045 Table *sqlite3ResultSetOfSelect(Parse *pParse, char *zTabName, Select *pSelect){
01046   Table *pTab;
01047   int i, j;
01048   ExprList *pEList;
01049   Column *aCol, *pCol;
01050 
01051   while( pSelect->pPrior ) pSelect = pSelect->pPrior;
01052   if( prepSelectStmt(pParse, pSelect) ){
01053     return 0;
01054   }
01055   if( sqlite3SelectResolve(pParse, pSelect, 0) ){
01056     return 0;
01057   }
01058   pTab = sqliteMalloc( sizeof(Table) );
01059   if( pTab==0 ){
01060     return 0;
01061   }
01062   pTab->nRef = 1;
01063   pTab->zName = zTabName ? sqliteStrDup(zTabName) : 0;
01064   pEList = pSelect->pEList;
01065   pTab->nCol = pEList->nExpr;
01066   assert( pTab->nCol>0 );
01067   pTab->aCol = aCol = sqliteMalloc( sizeof(pTab->aCol[0])*pTab->nCol );
01068   for(i=0, pCol=aCol; i<pTab->nCol; i++, pCol++){
01069     Expr *p, *pR;
01070     char *zType;
01071     char *zName;
01072     char *zBasename;
01073     CollSeq *pColl;
01074     int cnt;
01075     NameContext sNC;
01076     
01077     /* Get an appropriate name for the column
01078     */
01079     p = pEList->a[i].pExpr;
01080     assert( p->pRight==0 || p->pRight->token.z==0 || p->pRight->token.z[0]!=0 );
01081     if( (zName = pEList->a[i].zName)!=0 ){
01082       /* If the column contains an "AS <name>" phrase, use <name> as the name */
01083       zName = sqliteStrDup(zName);
01084     }else if( p->op==TK_DOT 
01085               && (pR=p->pRight)!=0 && pR->token.z && pR->token.z[0] ){
01086       /* For columns of the from A.B use B as the name */
01087       zName = sqlite3MPrintf("%T", &pR->token);
01088     }else if( p->span.z && p->span.z[0] ){
01089       /* Use the original text of the column expression as its name */
01090       zName = sqlite3MPrintf("%T", &p->span);
01091     }else{
01092       /* If all else fails, make up a name */
01093       zName = sqlite3MPrintf("column%d", i+1);
01094     }
01095     sqlite3Dequote(zName);
01096     if( sqlite3MallocFailed() ){
01097       sqliteFree(zName);
01098       sqlite3DeleteTable(0, pTab);
01099       return 0;
01100     }
01101 
01102     /* Make sure the column name is unique.  If the name is not unique,
01103     ** append a integer to the name so that it becomes unique.
01104     */
01105     zBasename = zName;
01106     for(j=cnt=0; j<i; j++){
01107       if( sqlite3StrICmp(aCol[j].zName, zName)==0 ){
01108         zName = sqlite3MPrintf("%s:%d", zBasename, ++cnt);
01109         j = -1;
01110         if( zName==0 ) break;
01111       }
01112     }
01113     if( zBasename!=zName ){
01114       sqliteFree(zBasename);
01115     }
01116     pCol->zName = zName;
01117 
01118     /* Get the typename, type affinity, and collating sequence for the
01119     ** column.
01120     */
01121     memset(&sNC, 0, sizeof(sNC));
01122     sNC.pSrcList = pSelect->pSrc;
01123     zType = sqliteStrDup(columnType(&sNC, p, 0, 0, 0));
01124     pCol->zType = zType;
01125     pCol->affinity = sqlite3ExprAffinity(p);
01126     pColl = sqlite3ExprCollSeq(pParse, p);
01127     if( pColl ){
01128       pCol->zColl = sqliteStrDup(pColl->zName);
01129     }
01130   }
01131   pTab->iPKey = -1;
01132   return pTab;
01133 }
01134 
01135 /*
01136 ** Prepare a SELECT statement for processing by doing the following
01137 ** things:
01138 **
01139 **    (1)  Make sure VDBE cursor numbers have been assigned to every
01140 **         element of the FROM clause.
01141 **
01142 **    (2)  Fill in the pTabList->a[].pTab fields in the SrcList that 
01143 **         defines FROM clause.  When views appear in the FROM clause,
01144 **         fill pTabList->a[].pSelect with a copy of the SELECT statement
01145 **         that implements the view.  A copy is made of the view's SELECT
01146 **         statement so that we can freely modify or delete that statement
01147 **         without worrying about messing up the presistent representation
01148 **         of the view.
01149 **
01150 **    (3)  Add terms to the WHERE clause to accomodate the NATURAL keyword
01151 **         on joins and the ON and USING clause of joins.
01152 **
01153 **    (4)  Scan the list of columns in the result set (pEList) looking
01154 **         for instances of the "*" operator or the TABLE.* operator.
01155 **         If found, expand each "*" to be every column in every table
01156 **         and TABLE.* to be every column in TABLE.
01157 **
01158 ** Return 0 on success.  If there are problems, leave an error message
01159 ** in pParse and return non-zero.
01160 */
01161 static int prepSelectStmt(Parse *pParse, Select *p){
01162   int i, j, k, rc;
01163   SrcList *pTabList;
01164   ExprList *pEList;
01165   struct SrcList_item *pFrom;
01166 
01167   if( p==0 || p->pSrc==0 || sqlite3MallocFailed() ){
01168     return 1;
01169   }
01170   pTabList = p->pSrc;
01171   pEList = p->pEList;
01172 
01173   /* Make sure cursor numbers have been assigned to all entries in
01174   ** the FROM clause of the SELECT statement.
01175   */
01176   sqlite3SrcListAssignCursors(pParse, p->pSrc);
01177 
01178   /* Look up every table named in the FROM clause of the select.  If
01179   ** an entry of the FROM clause is a subquery instead of a table or view,
01180   ** then create a transient table structure to describe the subquery.
01181   */
01182   for(i=0, pFrom=pTabList->a; i<pTabList->nSrc; i++, pFrom++){
01183     Table *pTab;
01184     if( pFrom->pTab!=0 ){
01185       /* This statement has already been prepared.  There is no need
01186       ** to go further. */
01187       assert( i==0 );
01188       return 0;
01189     }
01190     if( pFrom->zName==0 ){
01191 #ifndef SQLITE_OMIT_SUBQUERY
01192       /* A sub-query in the FROM clause of a SELECT */
01193       assert( pFrom->pSelect!=0 );
01194       if( pFrom->zAlias==0 ){
01195         pFrom->zAlias =
01196           sqlite3MPrintf("sqlite_subquery_%p_", (void*)pFrom->pSelect);
01197       }
01198       assert( pFrom->pTab==0 );
01199       pFrom->pTab = pTab = 
01200         sqlite3ResultSetOfSelect(pParse, pFrom->zAlias, pFrom->pSelect);
01201       if( pTab==0 ){
01202         return 1;
01203       }
01204       /* The isTransient flag indicates that the Table structure has been
01205       ** dynamically allocated and may be freed at any time.  In other words,
01206       ** pTab is not pointing to a persistent table structure that defines
01207       ** part of the schema. */
01208       pTab->isTransient = 1;
01209 #endif
01210     }else{
01211       /* An ordinary table or view name in the FROM clause */
01212       assert( pFrom->pTab==0 );
01213       pFrom->pTab = pTab = 
01214         sqlite3LocateTable(pParse,pFrom->zName,pFrom->zDatabase);
01215       if( pTab==0 ){
01216         return 1;
01217       }
01218       pTab->nRef++;
01219 #ifndef SQLITE_OMIT_VIEW
01220       if( pTab->pSelect ){
01221         /* We reach here if the named table is a really a view */
01222         if( sqlite3ViewGetColumnNames(pParse, pTab) ){
01223           return 1;
01224         }
01225         /* If pFrom->pSelect!=0 it means we are dealing with a
01226         ** view within a view.  The SELECT structure has already been
01227         ** copied by the outer view so we can skip the copy step here
01228         ** in the inner view.
01229         */
01230         if( pFrom->pSelect==0 ){
01231           pFrom->pSelect = sqlite3SelectDup(pTab->pSelect);
01232         }
01233       }
01234 #endif
01235     }
01236   }
01237 
01238   /* Process NATURAL keywords, and ON and USING clauses of joins.
01239   */
01240   if( sqliteProcessJoin(pParse, p) ) return 1;
01241 
01242   /* For every "*" that occurs in the column list, insert the names of
01243   ** all columns in all tables.  And for every TABLE.* insert the names
01244   ** of all columns in TABLE.  The parser inserted a special expression
01245   ** with the TK_ALL operator for each "*" that it found in the column list.
01246   ** The following code just has to locate the TK_ALL expressions and expand
01247   ** each one to the list of all columns in all tables.
01248   **
01249   ** The first loop just checks to see if there are any "*" operators
01250   ** that need expanding.
01251   */
01252   for(k=0; k<pEList->nExpr; k++){
01253     Expr *pE = pEList->a[k].pExpr;
01254     if( pE->op==TK_ALL ) break;
01255     if( pE->op==TK_DOT && pE->pRight && pE->pRight->op==TK_ALL
01256          && pE->pLeft && pE->pLeft->op==TK_ID ) break;
01257   }
01258   rc = 0;
01259   if( k<pEList->nExpr ){
01260     /*
01261     ** If we get here it means the result set contains one or more "*"
01262     ** operators that need to be expanded.  Loop through each expression
01263     ** in the result set and expand them one by one.
01264     */
01265     struct ExprList_item *a = pEList->a;
01266     ExprList *pNew = 0;
01267     int flags = pParse->db->flags;
01268     int longNames = (flags & SQLITE_FullColNames)!=0 &&
01269                       (flags & SQLITE_ShortColNames)==0;
01270 
01271     for(k=0; k<pEList->nExpr; k++){
01272       Expr *pE = a[k].pExpr;
01273       if( pE->op!=TK_ALL &&
01274            (pE->op!=TK_DOT || pE->pRight==0 || pE->pRight->op!=TK_ALL) ){
01275         /* This particular expression does not need to be expanded.
01276         */
01277         pNew = sqlite3ExprListAppend(pNew, a[k].pExpr, 0);
01278         if( pNew ){
01279           pNew->a[pNew->nExpr-1].zName = a[k].zName;
01280         }else{
01281           rc = 1;
01282         }
01283         a[k].pExpr = 0;
01284         a[k].zName = 0;
01285       }else{
01286         /* This expression is a "*" or a "TABLE.*" and needs to be
01287         ** expanded. */
01288         int tableSeen = 0;      /* Set to 1 when TABLE matches */
01289         char *zTName;            /* text of name of TABLE */
01290         if( pE->op==TK_DOT && pE->pLeft ){
01291           zTName = sqlite3NameFromToken(&pE->pLeft->token);
01292         }else{
01293           zTName = 0;
01294         }
01295         for(i=0, pFrom=pTabList->a; i<pTabList->nSrc; i++, pFrom++){
01296           Table *pTab = pFrom->pTab;
01297           char *zTabName = pFrom->zAlias;
01298           if( zTabName==0 || zTabName[0]==0 ){ 
01299             zTabName = pTab->zName;
01300           }
01301           if( zTName && (zTabName==0 || zTabName[0]==0 || 
01302                  sqlite3StrICmp(zTName, zTabName)!=0) ){
01303             continue;
01304           }
01305           tableSeen = 1;
01306           for(j=0; j<pTab->nCol; j++){
01307             Expr *pExpr, *pRight;
01308             char *zName = pTab->aCol[j].zName;
01309 
01310             if( i>0 ){
01311               struct SrcList_item *pLeft = &pTabList->a[i-1];
01312               if( (pLeft->jointype & JT_NATURAL)!=0 &&
01313                         columnIndex(pLeft->pTab, zName)>=0 ){
01314                 /* In a NATURAL join, omit the join columns from the 
01315                 ** table on the right */
01316                 continue;
01317               }
01318               if( sqlite3IdListIndex(pLeft->pUsing, zName)>=0 ){
01319                 /* In a join with a USING clause, omit columns in the
01320                 ** using clause from the table on the right. */
01321                 continue;
01322               }
01323             }
01324             pRight = sqlite3Expr(TK_ID, 0, 0, 0);
01325             if( pRight==0 ) break;
01326             setToken(&pRight->token, zName);
01327             if( zTabName && (longNames || pTabList->nSrc>1) ){
01328               Expr *pLeft = sqlite3Expr(TK_ID, 0, 0, 0);
01329               pExpr = sqlite3Expr(TK_DOT, pLeft, pRight, 0);
01330               if( pExpr==0 ) break;
01331               setToken(&pLeft->token, zTabName);
01332               setToken(&pExpr->span, sqlite3MPrintf("%s.%s", zTabName, zName));
01333               pExpr->span.dyn = 1;
01334               pExpr->token.z = 0;
01335               pExpr->token.n = 0;
01336               pExpr->token.dyn = 0;
01337             }else{
01338               pExpr = pRight;
01339               pExpr->span = pExpr->token;
01340             }
01341             if( longNames ){
01342               pNew = sqlite3ExprListAppend(pNew, pExpr, &pExpr->span);
01343             }else{
01344               pNew = sqlite3ExprListAppend(pNew, pExpr, &pRight->token);
01345             }
01346           }
01347         }
01348         if( !tableSeen ){
01349           if( zTName ){
01350             sqlite3ErrorMsg(pParse, "no such table: %s", zTName);
01351           }else{
01352             sqlite3ErrorMsg(pParse, "no tables specified");
01353           }
01354           rc = 1;
01355         }
01356         sqliteFree(zTName);
01357       }
01358     }
01359     sqlite3ExprListDelete(pEList);
01360     p->pEList = pNew;
01361   }
01362   return rc;
01363 }
01364 
01365 #ifndef SQLITE_OMIT_COMPOUND_SELECT
01366 /*
01367 ** This routine associates entries in an ORDER BY expression list with
01368 ** columns in a result.  For each ORDER BY expression, the opcode of
01369 ** the top-level node is changed to TK_COLUMN and the iColumn value of
01370 ** the top-level node is filled in with column number and the iTable
01371 ** value of the top-level node is filled with iTable parameter.
01372 **
01373 ** If there are prior SELECT clauses, they are processed first.  A match
01374 ** in an earlier SELECT takes precedence over a later SELECT.
01375 **
01376 ** Any entry that does not match is flagged as an error.  The number
01377 ** of errors is returned.
01378 */
01379 static int matchOrderbyToColumn(
01380   Parse *pParse,          /* A place to leave error messages */
01381   Select *pSelect,        /* Match to result columns of this SELECT */
01382   ExprList *pOrderBy,     /* The ORDER BY values to match against columns */
01383   int iTable,             /* Insert this value in iTable */
01384   int mustComplete        /* If TRUE all ORDER BYs must match */
01385 ){
01386   int nErr = 0;
01387   int i, j;
01388   ExprList *pEList;
01389 
01390   if( pSelect==0 || pOrderBy==0 ) return 1;
01391   if( mustComplete ){
01392     for(i=0; i<pOrderBy->nExpr; i++){ pOrderBy->a[i].done = 0; }
01393   }
01394   if( prepSelectStmt(pParse, pSelect) ){
01395     return 1;
01396   }
01397   if( pSelect->pPrior ){
01398     if( matchOrderbyToColumn(pParse, pSelect->pPrior, pOrderBy, iTable, 0) ){
01399       return 1;
01400     }
01401   }
01402   pEList = pSelect->pEList;
01403   for(i=0; i<pOrderBy->nExpr; i++){
01404     Expr *pE = pOrderBy->a[i].pExpr;
01405     int iCol = -1;
01406     if( pOrderBy->a[i].done ) continue;
01407     if( sqlite3ExprIsInteger(pE, &iCol) ){
01408       if( iCol<=0 || iCol>pEList->nExpr ){
01409         sqlite3ErrorMsg(pParse,
01410           "ORDER BY position %d should be between 1 and %d",
01411           iCol, pEList->nExpr);
01412         nErr++;
01413         break;
01414       }
01415       if( !mustComplete ) continue;
01416       iCol--;
01417     }
01418     for(j=0; iCol<0 && j<pEList->nExpr; j++){
01419       if( pEList->a[j].zName && (pE->op==TK_ID || pE->op==TK_STRING) ){
01420         char *zName, *zLabel;
01421         zName = pEList->a[j].zName;
01422         zLabel = sqlite3NameFromToken(&pE->token);
01423         assert( zLabel!=0 );
01424         if( sqlite3StrICmp(zName, zLabel)==0 ){ 
01425           iCol = j;
01426         }
01427         sqliteFree(zLabel);
01428       }
01429       if( iCol<0 && sqlite3ExprCompare(pE, pEList->a[j].pExpr) ){
01430         iCol = j;
01431       }
01432     }
01433     if( iCol>=0 ){
01434       pE->op = TK_COLUMN;
01435       pE->iColumn = iCol;
01436       pE->iTable = iTable;
01437       pE->iAgg = -1;
01438       pOrderBy->a[i].done = 1;
01439     }
01440     if( iCol<0 && mustComplete ){
01441       sqlite3ErrorMsg(pParse,
01442         "ORDER BY term number %d does not match any result column", i+1);
01443       nErr++;
01444       break;
01445     }
01446   }
01447   return nErr;  
01448 }
01449 #endif /* #ifndef SQLITE_OMIT_COMPOUND_SELECT */
01450 
01451 /*
01452 ** Get a VDBE for the given parser context.  Create a new one if necessary.
01453 ** If an error occurs, return NULL and leave a message in pParse.
01454 */
01455 Vdbe *sqlite3GetVdbe(Parse *pParse){
01456   Vdbe *v = pParse->pVdbe;
01457   if( v==0 ){
01458     v = pParse->pVdbe = sqlite3VdbeCreate(pParse->db);
01459   }
01460   return v;
01461 }
01462 
01463 
01464 /*
01465 ** Compute the iLimit and iOffset fields of the SELECT based on the
01466 ** pLimit and pOffset expressions.  pLimit and pOffset hold the expressions
01467 ** that appear in the original SQL statement after the LIMIT and OFFSET
01468 ** keywords.  Or NULL if those keywords are omitted. iLimit and iOffset 
01469 ** are the integer memory register numbers for counters used to compute 
01470 ** the limit and offset.  If there is no limit and/or offset, then 
01471 ** iLimit and iOffset are negative.
01472 **
01473 ** This routine changes the values of iLimit and iOffset only if
01474 ** a limit or offset is defined by pLimit and pOffset.  iLimit and
01475 ** iOffset should have been preset to appropriate default values
01476 ** (usually but not always -1) prior to calling this routine.
01477 ** Only if pLimit!=0 or pOffset!=0 do the limit registers get
01478 ** redefined.  The UNION ALL operator uses this property to force
01479 ** the reuse of the same limit and offset registers across multiple
01480 ** SELECT statements.
01481 */
01482 static void computeLimitRegisters(Parse *pParse, Select *p, int iBreak){
01483   Vdbe *v = 0;
01484   int iLimit = 0;
01485   int iOffset;
01486   int addr1, addr2;
01487 
01488   /* 
01489   ** "LIMIT -1" always shows all rows.  There is some
01490   ** contraversy about what the correct behavior should be.
01491   ** The current implementation interprets "LIMIT 0" to mean
01492   ** no rows.
01493   */
01494   if( p->pLimit ){
01495     p->iLimit = iLimit = pParse->nMem;
01496     pParse->nMem += 2;
01497     v = sqlite3GetVdbe(pParse);
01498     if( v==0 ) return;
01499     sqlite3ExprCode(pParse, p->pLimit);
01500     sqlite3VdbeAddOp(v, OP_MustBeInt, 0, 0);
01501     sqlite3VdbeAddOp(v, OP_MemStore, iLimit, 0);
01502     VdbeComment((v, "# LIMIT counter"));
01503     sqlite3VdbeAddOp(v, OP_IfMemZero, iLimit, iBreak);
01504   }
01505   if( p->pOffset ){
01506     p->iOffset = iOffset = pParse->nMem++;
01507     v = sqlite3GetVdbe(pParse);
01508     if( v==0 ) return;
01509     sqlite3ExprCode(pParse, p->pOffset);
01510     sqlite3VdbeAddOp(v, OP_MustBeInt, 0, 0);
01511     sqlite3VdbeAddOp(v, OP_MemStore, iOffset, p->pLimit==0);
01512     VdbeComment((v, "# OFFSET counter"));
01513     addr1 = sqlite3VdbeAddOp(v, OP_IfMemPos, iOffset, 0);
01514     sqlite3VdbeAddOp(v, OP_Pop, 1, 0);
01515     sqlite3VdbeAddOp(v, OP_Integer, 0, 0);
01516     sqlite3VdbeJumpHere(v, addr1);
01517     if( p->pLimit ){
01518       sqlite3VdbeAddOp(v, OP_Add, 0, 0);
01519     }
01520   }
01521   if( p->pLimit ){
01522     addr1 = sqlite3VdbeAddOp(v, OP_IfMemPos, iLimit, 0);
01523     sqlite3VdbeAddOp(v, OP_Pop, 1, 0);
01524     sqlite3VdbeAddOp(v, OP_MemInt, -1, iLimit+1);
01525     addr2 = sqlite3VdbeAddOp(v, OP_Goto, 0, 0);
01526     sqlite3VdbeJumpHere(v, addr1);
01527     sqlite3VdbeAddOp(v, OP_MemStore, iLimit+1, 1);
01528     VdbeComment((v, "# LIMIT+OFFSET"));
01529     sqlite3VdbeJumpHere(v, addr2);
01530   }
01531 }
01532 
01533 /*
01534 ** Allocate a virtual index to use for sorting.
01535 */
01536 static void createSortingIndex(Parse *pParse, Select *p, ExprList *pOrderBy){
01537   if( pOrderBy ){
01538     int addr;
01539     assert( pOrderBy->iECursor==0 );
01540     pOrderBy->iECursor = pParse->nTab++;
01541     addr = sqlite3VdbeAddOp(pParse->pVdbe, OP_OpenVirtual,
01542                             pOrderBy->iECursor, pOrderBy->nExpr+1);
01543     assert( p->addrOpenVirt[2] == -1 );
01544     p->addrOpenVirt[2] = addr;
01545   }
01546 }
01547 
01548 #ifndef SQLITE_OMIT_COMPOUND_SELECT
01549 /*
01550 ** Return the appropriate collating sequence for the iCol-th column of
01551 ** the result set for the compound-select statement "p".  Return NULL if
01552 ** the column has no default collating sequence.
01553 **
01554 ** The collating sequence for the compound select is taken from the
01555 ** left-most term of the select that has a collating sequence.
01556 */
01557 static CollSeq *multiSelectCollSeq(Parse *pParse, Select *p, int iCol){
01558   CollSeq *pRet;
01559   if( p->pPrior ){
01560     pRet = multiSelectCollSeq(pParse, p->pPrior, iCol);
01561   }else{
01562     pRet = 0;
01563   }
01564   if( pRet==0 ){
01565     pRet = sqlite3ExprCollSeq(pParse, p->pEList->a[iCol].pExpr);
01566   }
01567   return pRet;
01568 }
01569 #endif /* SQLITE_OMIT_COMPOUND_SELECT */
01570 
01571 #ifndef SQLITE_OMIT_COMPOUND_SELECT
01572 /*
01573 ** This routine is called to process a query that is really the union
01574 ** or intersection of two or more separate queries.
01575 **
01576 ** "p" points to the right-most of the two queries.  the query on the
01577 ** left is p->pPrior.  The left query could also be a compound query
01578 ** in which case this routine will be called recursively. 
01579 **
01580 ** The results of the total query are to be written into a destination
01581 ** of type eDest with parameter iParm.
01582 **
01583 ** Example 1:  Consider a three-way compound SQL statement.
01584 **
01585 **     SELECT a FROM t1 UNION SELECT b FROM t2 UNION SELECT c FROM t3
01586 **
01587 ** This statement is parsed up as follows:
01588 **
01589 **     SELECT c FROM t3
01590 **      |
01591 **      `----->  SELECT b FROM t2
01592 **                |
01593 **                `------>  SELECT a FROM t1
01594 **
01595 ** The arrows in the diagram above represent the Select.pPrior pointer.
01596 ** So if this routine is called with p equal to the t3 query, then
01597 ** pPrior will be the t2 query.  p->op will be TK_UNION in this case.
01598 **
01599 ** Notice that because of the way SQLite parses compound SELECTs, the
01600 ** individual selects always group from left to right.
01601 */
01602 static int multiSelect(
01603   Parse *pParse,        /* Parsing context */
01604   Select *p,            /* The right-most of SELECTs to be coded */
01605   int eDest,            /* \___  Store query results as specified */
01606   int iParm,            /* /     by these two parameters.         */
01607   char *aff             /* If eDest is SRT_Union, the affinity string */
01608 ){
01609   int rc = SQLITE_OK;   /* Success code from a subroutine */
01610   Select *pPrior;       /* Another SELECT immediately to our left */
01611   Vdbe *v;              /* Generate code to this VDBE */
01612   int nCol;             /* Number of columns in the result set */
01613   ExprList *pOrderBy;   /* The ORDER BY clause on p */
01614   int aSetP2[2];        /* Set P2 value of these op to number of columns */
01615   int nSetP2 = 0;       /* Number of slots in aSetP2[] used */
01616 
01617   /* Make sure there is no ORDER BY or LIMIT clause on prior SELECTs.  Only
01618   ** the last (right-most) SELECT in the series may have an ORDER BY or LIMIT.
01619   */
01620   if( p==0 || p->pPrior==0 ){
01621     rc = 1;
01622     goto multi_select_end;
01623   }
01624   pPrior = p->pPrior;
01625   assert( pPrior->pRightmost!=pPrior );
01626   assert( pPrior->pRightmost==p->pRightmost );
01627   if( pPrior->pOrderBy ){
01628     sqlite3ErrorMsg(pParse,"ORDER BY clause should come after %s not before",
01629       selectOpName(p->op));
01630     rc = 1;
01631     goto multi_select_end;
01632   }
01633   if( pPrior->pLimit ){
01634     sqlite3ErrorMsg(pParse,"LIMIT clause should come after %s not before",
01635       selectOpName(p->op));
01636     rc = 1;
01637     goto multi_select_end;
01638   }
01639 
01640   /* Make sure we have a valid query engine.  If not, create a new one.
01641   */
01642   v = sqlite3GetVdbe(pParse);
01643   if( v==0 ){
01644     rc = 1;
01645     goto multi_select_end;
01646   }
01647 
01648   /* Create the destination temporary table if necessary
01649   */
01650   if( eDest==SRT_VirtualTab ){
01651     assert( p->pEList );
01652     assert( nSetP2<sizeof(aSetP2)/sizeof(aSetP2[0]) );
01653     aSetP2[nSetP2++] = sqlite3VdbeAddOp(v, OP_OpenVirtual, iParm, 0);
01654     eDest = SRT_Table;
01655   }
01656 
01657   /* Generate code for the left and right SELECT statements.
01658   */
01659   pOrderBy = p->pOrderBy;
01660   switch( p->op ){
01661     case TK_ALL: {
01662       if( pOrderBy==0 ){
01663         int addr = 0;
01664         assert( !pPrior->pLimit );
01665         pPrior->pLimit = p->pLimit;
01666         pPrior->pOffset = p->pOffset;
01667         rc = sqlite3Select(pParse, pPrior, eDest, iParm, 0, 0, 0, aff);
01668         p->pLimit = 0;
01669         p->pOffset = 0;
01670         if( rc ){
01671           goto multi_select_end;
01672         }
01673         p->pPrior = 0;
01674         p->iLimit = pPrior->iLimit;
01675         p->iOffset = pPrior->iOffset;
01676         if( p->iLimit>=0 ){
01677           addr = sqlite3VdbeAddOp(v, OP_IfMemZero, p->iLimit, 0);
01678           VdbeComment((v, "# Jump ahead if LIMIT reached"));
01679         }
01680         rc = sqlite3Select(pParse, p, eDest, iParm, 0, 0, 0, aff);
01681         p->pPrior = pPrior;
01682         if( rc ){
01683           goto multi_select_end;
01684         }
01685         if( addr ){
01686           sqlite3VdbeJumpHere(v, addr);
01687         }
01688         break;
01689       }
01690       /* For UNION ALL ... ORDER BY fall through to the next case */
01691     }
01692     case TK_EXCEPT:
01693     case TK_UNION: {
01694       int unionTab;    /* Cursor number of the temporary table holding result */
01695       int op = 0;      /* One of the SRT_ operations to apply to self */
01696       int priorOp;     /* The SRT_ operation to apply to prior selects */
01697       Expr *pLimit, *pOffset; /* Saved values of p->nLimit and p->nOffset */
01698       int addr;
01699 
01700       priorOp = p->op==TK_ALL ? SRT_Table : SRT_Union;
01701       if( eDest==priorOp && pOrderBy==0 && !p->pLimit && !p->pOffset ){
01702         /* We can reuse a temporary table generated by a SELECT to our
01703         ** right.
01704         */
01705         unionTab = iParm;
01706       }else{
01707         /* We will need to create our own temporary table to hold the
01708         ** intermediate results.
01709         */
01710         unionTab = pParse->nTab++;
01711         if( pOrderBy && matchOrderbyToColumn(pParse, p, pOrderBy, unionTab,1) ){
01712           rc = 1;
01713           goto multi_select_end;
01714         }
01715         addr = sqlite3VdbeAddOp(v, OP_OpenVirtual, unionTab, 0);
01716         if( priorOp==SRT_Table ){
01717           assert( nSetP2<sizeof(aSetP2)/sizeof(aSetP2[0]) );
01718           aSetP2[nSetP2++] = addr;
01719         }else{
01720           assert( p->addrOpenVirt[0] == -1 );
01721           p->addrOpenVirt[0] = addr;
01722           p->pRightmost->usesVirt = 1;
01723         }
01724         createSortingIndex(pParse, p, pOrderBy);
01725         assert( p->pEList );
01726       }
01727 
01728       /* Code the SELECT statements to our left
01729       */
01730       assert( !pPrior->pOrderBy );
01731       rc = sqlite3Select(pParse, pPrior, priorOp, unionTab, 0, 0, 0, aff);
01732       if( rc ){
01733         goto multi_select_end;
01734       }
01735 
01736       /* Code the current SELECT statement
01737       */
01738       switch( p->op ){
01739          case TK_EXCEPT:  op = SRT_Except;   break;
01740          case TK_UNION:   op = SRT_Union;    break;
01741          case TK_ALL:     op = SRT_Table;    break;
01742       }
01743       p->pPrior = 0;
01744       p->pOrderBy = 0;
01745       p->disallowOrderBy = pOrderBy!=0;
01746       pLimit = p->pLimit;
01747       p->pLimit = 0;
01748       pOffset = p->pOffset;
01749       p->pOffset = 0;
01750       rc = sqlite3Select(pParse, p, op, unionTab, 0, 0, 0, aff);
01751       p->pPrior = pPrior;
01752       p->pOrderBy = pOrderBy;
01753       sqlite3ExprDelete(p->pLimit);
01754       p->pLimit = pLimit;
01755       p->pOffset = pOffset;
01756       p->iLimit = -1;
01757       p->iOffset = -1;
01758       if( rc ){
01759         goto multi_select_end;
01760       }
01761 
01762 
01763       /* Convert the data in the temporary table into whatever form
01764       ** it is that we currently need.
01765       */      
01766       if( eDest!=priorOp || unionTab!=iParm ){
01767         int iCont, iBreak, iStart;
01768         assert( p->pEList );
01769         if( eDest==SRT_Callback ){
01770           Select *pFirst = p;
01771           while( pFirst->pPrior ) pFirst = pFirst->pPrior;
01772           generateColumnNames(pParse, 0, pFirst->pEList);
01773         }
01774         iBreak = sqlite3VdbeMakeLabel(v);
01775         iCont = sqlite3VdbeMakeLabel(v);
01776         computeLimitRegisters(pParse, p, iBreak);
01777         sqlite3VdbeAddOp(v, OP_Rewind, unionTab, iBreak);
01778         iStart = sqlite3VdbeCurrentAddr(v);
01779         rc = selectInnerLoop(pParse, p, p->pEList, unionTab, p->pEList->nExpr,
01780                              pOrderBy, -1, eDest, iParm, 
01781                              iCont, iBreak, 0);
01782         if( rc ){
01783           rc = 1;
01784           goto multi_select_end;
01785         }
01786         sqlite3VdbeResolveLabel(v, iCont);
01787         sqlite3VdbeAddOp(v, OP_Next, unionTab, iStart);
01788         sqlite3VdbeResolveLabel(v, iBreak);
01789         sqlite3VdbeAddOp(v, OP_Close, unionTab, 0);
01790       }
01791       break;
01792     }
01793     case TK_INTERSECT: {
01794       int tab1, tab2;
01795       int iCont, iBreak, iStart;
01796       Expr *pLimit, *pOffset;
01797       int addr;
01798 
01799       /* INTERSECT is different from the others since it requires
01800       ** two temporary tables.  Hence it has its own case.  Begin
01801       ** by allocating the tables we will need.
01802       */
01803       tab1 = pParse->nTab++;
01804       tab2 = pParse->nTab++;
01805       if( pOrderBy && matchOrderbyToColumn(pParse,p,pOrderBy,tab1,1) ){
01806         rc = 1;
01807         goto multi_select_end;
01808       }
01809       createSortingIndex(pParse, p, pOrderBy);
01810 
01811       addr = sqlite3VdbeAddOp(v, OP_OpenVirtual, tab1, 0);
01812       assert( p->addrOpenVirt[0] == -1 );
01813       p->addrOpenVirt[0] = addr;
01814       p->pRightmost->usesVirt = 1;
01815       assert( p->pEList );
01816 
01817       /* Code the SELECTs to our left into temporary table "tab1".
01818       */
01819       rc = sqlite3Select(pParse, pPrior, SRT_Union, tab1, 0, 0, 0, aff);
01820       if( rc ){
01821         goto multi_select_end;
01822       }
01823 
01824       /* Code the current SELECT into temporary table "tab2"
01825       */
01826       addr = sqlite3VdbeAddOp(v, OP_OpenVirtual, tab2, 0);
01827       assert( p->addrOpenVirt[1] == -1 );
01828       p->addrOpenVirt[1] = addr;
01829       p->pPrior = 0;
01830       pLimit = p->pLimit;
01831       p->pLimit = 0;
01832       pOffset = p->pOffset;
01833       p->pOffset = 0;
01834       rc = sqlite3Select(pParse, p, SRT_Union, tab2, 0, 0, 0, aff);
01835       p->pPrior = pPrior;
01836       sqlite3ExprDelete(p->pLimit);
01837       p->pLimit = pLimit;
01838       p->pOffset = pOffset;
01839       if( rc ){
01840         goto multi_select_end;
01841       }
01842 
01843       /* Generate code to take the intersection of the two temporary
01844       ** tables.
01845       */
01846       assert( p->pEList );
01847       if( eDest==SRT_Callback ){
01848         Select *pFirst = p;
01849         while( pFirst->pPrior ) pFirst = pFirst->pPrior;
01850         generateColumnNames(pParse, 0, pFirst->pEList);
01851       }
01852       iBreak = sqlite3VdbeMakeLabel(v);
01853       iCont = sqlite3VdbeMakeLabel(v);
01854       computeLimitRegisters(pParse, p, iBreak);
01855       sqlite3VdbeAddOp(v, OP_Rewind, tab1, iBreak);
01856       iStart = sqlite3VdbeAddOp(v, OP_RowKey, tab1, 0);
01857       sqlite3VdbeAddOp(v, OP_NotFound, tab2, iCont);
01858       rc = selectInnerLoop(pParse, p, p->pEList, tab1, p->pEList->nExpr,
01859                              pOrderBy, -1, eDest, iParm, 
01860                              iCont, iBreak, 0);
01861       if( rc ){
01862         rc = 1;
01863         goto multi_select_end;
01864       }
01865       sqlite3VdbeResolveLabel(v, iCont);
01866       sqlite3VdbeAddOp(v, OP_Next, tab1, iStart);
01867       sqlite3VdbeResolveLabel(v, iBreak);
01868       sqlite3VdbeAddOp(v, OP_Close, tab2, 0);
01869       sqlite3VdbeAddOp(v, OP_Close, tab1, 0);
01870       break;
01871     }
01872   }
01873 
01874   /* Make sure all SELECTs in the statement have the same number of elements
01875   ** in their result sets.
01876   */
01877   assert( p->pEList && pPrior->pEList );
01878   if( p->pEList->nExpr!=pPrior->pEList->nExpr ){
01879     sqlite3ErrorMsg(pParse, "SELECTs to the left and right of %s"
01880       " do not have the same number of result columns", selectOpName(p->op));
01881     rc = 1;
01882     goto multi_select_end;
01883   }
01884 
01885   /* Set the number of columns in temporary tables
01886   */
01887   nCol = p->pEList->nExpr;
01888   while( nSetP2 ){
01889     sqlite3VdbeChangeP2(v, aSetP2[--nSetP2], nCol);
01890   }
01891 
01892   /* Compute collating sequences used by either the ORDER BY clause or
01893   ** by any temporary tables needed to implement the compound select.
01894   ** Attach the KeyInfo structure to all temporary tables.  Invoke the
01895   ** ORDER BY processing if there is an ORDER BY clause.
01896   **
01897   ** This section is run by the right-most SELECT statement only.
01898   ** SELECT statements to the left always skip this part.  The right-most
01899   ** SELECT might also skip this part if it has no ORDER BY clause and
01900   ** no temp tables are required.
01901   */
01902   if( pOrderBy || p->usesVirt ){
01903     int i;                        /* Loop counter */
01904     KeyInfo *pKeyInfo;            /* Collating sequence for the result set */
01905     Select *pLoop;                /* For looping through SELECT statements */
01906     CollSeq **apColl;
01907     CollSeq **aCopy;
01908 
01909     assert( p->pRightmost==p );
01910     pKeyInfo = sqliteMalloc(sizeof(*pKeyInfo)+nCol*2*sizeof(CollSeq*) + nCol);
01911     if( !pKeyInfo ){
01912       rc = SQLITE_NOMEM;
01913       goto multi_select_end;
01914     }
01915 
01916     pKeyInfo->enc = ENC(pParse->db);
01917     pKeyInfo->nField = nCol;
01918 
01919     for(i=0, apColl=pKeyInfo->aColl; i<nCol; i++, apColl++){
01920       *apColl = multiSelectCollSeq(pParse, p, i);
01921       if( 0==*apColl ){
01922         *apColl = pParse->db->pDfltColl;
01923       }
01924     }
01925 
01926     for(pLoop=p; pLoop; pLoop=pLoop->pPrior){
01927       for(i=0; i<2; i++){
01928         int addr = pLoop->addrOpenVirt[i];
01929         if( addr<0 ){
01930           /* If [0] is unused then [1] is also unused.  So we can
01931           ** always safely abort as soon as the first unused slot is found */
01932           assert( pLoop->addrOpenVirt[1]<0 );
01933           break;
01934         }
01935         sqlite3VdbeChangeP2(v, addr, nCol);
01936         sqlite3VdbeChangeP3(v, addr, (char*)pKeyInfo, P3_KEYINFO);
01937       }
01938     }
01939 
01940     if( pOrderBy ){
01941       struct ExprList_item *pOTerm = pOrderBy->a;
01942       int nOrderByExpr = pOrderBy->nExpr;
01943       int addr;
01944       u8 *pSortOrder;
01945 
01946       aCopy = &pKeyInfo->aColl[nCol];
01947       pSortOrder = pKeyInfo->aSortOrder = (u8*)&aCopy[nCol];
01948       memcpy(aCopy, pKeyInfo->aColl, nCol*sizeof(CollSeq*));
01949       apColl = pKeyInfo->aColl;
01950       for(i=0; i<nOrderByExpr; i++, pOTerm++, apColl++, pSortOrder++){
01951         Expr *pExpr = pOTerm->pExpr;
01952         char *zName = pOTerm->zName;
01953         assert( pExpr->op==TK_COLUMN && pExpr->iColumn<nCol );
01954         if( zName ){
01955           *apColl = sqlite3LocateCollSeq(pParse, zName, -1);
01956         }else{
01957           *apColl = aCopy[pExpr->iColumn];
01958         }
01959         *pSortOrder = pOTerm->sortOrder;
01960       }
01961       assert( p->pRightmost==p );
01962       assert( p->addrOpenVirt[2]>=0 );
01963       addr = p->addrOpenVirt[2];
01964       sqlite3VdbeChangeP2(v, addr, p->pEList->nExpr+2);
01965       pKeyInfo->nField = nOrderByExpr;
01966       sqlite3VdbeChangeP3(v, addr, (char*)pKeyInfo, P3_KEYINFO_HANDOFF);
01967       pKeyInfo = 0;
01968       generateSortTail(pParse, p, v, p->pEList->nExpr, eDest, iParm);
01969     }
01970 
01971     sqliteFree(pKeyInfo);
01972   }
01973 
01974 multi_select_end:
01975   return rc;
01976 }
01977 #endif /* SQLITE_OMIT_COMPOUND_SELECT */
01978 
01979 #ifndef SQLITE_OMIT_VIEW
01980 /*
01981 ** Scan through the expression pExpr.  Replace every reference to
01982 ** a column in table number iTable with a copy of the iColumn-th
01983 ** entry in pEList.  (But leave references to the ROWID column 
01984 ** unchanged.)
01985 **
01986 ** This routine is part of the flattening procedure.  A subquery
01987 ** whose result set is defined by pEList appears as entry in the
01988 ** FROM clause of a SELECT such that the VDBE cursor assigned to that
01989 ** FORM clause entry is iTable.  This routine make the necessary 
01990 ** changes to pExpr so that it refers directly to the source table
01991 ** of the subquery rather the result set of the subquery.
01992 */
01993 static void substExprList(ExprList*,int,ExprList*);  /* Forward Decl */
01994 static void substSelect(Select *, int, ExprList *);  /* Forward Decl */
01995 static void substExpr(Expr *pExpr, int iTable, ExprList *pEList){
01996   if( pExpr==0 ) return;
01997   if( pExpr->op==TK_COLUMN && pExpr->iTable==iTable ){
01998     if( pExpr->iColumn<0 ){
01999       pExpr->op = TK_NULL;
02000     }else{
02001       Expr *pNew;
02002       assert( pEList!=0 && pExpr->iColumn<pEList->nExpr );
02003       assert( pExpr->pLeft==0 && pExpr->pRight==0 && pExpr->pList==0 );
02004       pNew = pEList->a[pExpr->iColumn].pExpr;
02005       assert( pNew!=0 );
02006       pExpr->op = pNew->op;
02007       assert( pExpr->pLeft==0 );
02008       pExpr->pLeft = sqlite3ExprDup(pNew->pLeft);
02009       assert( pExpr->pRight==0 );
02010       pExpr->pRight = sqlite3ExprDup(pNew->pRight);
02011       assert( pExpr->pList==0 );
02012       pExpr->pList = sqlite3ExprListDup(pNew->pList);
02013       pExpr->iTable = pNew->iTable;
02014       pExpr->iColumn = pNew->iColumn;
02015       pExpr->iAgg = pNew->iAgg;
02016       sqlite3TokenCopy(&pExpr->token, &pNew->token);
02017       sqlite3TokenCopy(&pExpr->span, &pNew->span);
02018       pExpr->pSelect = sqlite3SelectDup(pNew->pSelect);
02019       pExpr->flags = pNew->flags;
02020     }
02021   }else{
02022     substExpr(pExpr->pLeft, iTable, pEList);
02023     substExpr(pExpr->pRight, iTable, pEList);
02024     substSelect(pExpr->pSelect, iTable, pEList);
02025     substExprList(pExpr->pList, iTable, pEList);
02026   }
02027 }
02028 static void substExprList(ExprList *pList, int iTable, ExprList *pEList){
02029   int i;
02030   if( pList==0 ) return;
02031   for(i=0; i<pList->nExpr; i++){
02032     substExpr(pList->a[i].pExpr, iTable, pEList);
02033   }
02034 }
02035 static void substSelect(Select *p, int iTable, ExprList *pEList){
02036   if( !p ) return;
02037   substExprList(p->pEList, iTable, pEList);
02038   substExprList(p->pGroupBy, iTable, pEList);
02039   substExprList(p->pOrderBy, iTable, pEList);
02040   substExpr(p->pHaving, iTable, pEList);
02041   substExpr(p->pWhere, iTable, pEList);
02042 }
02043 #endif /* !defined(SQLITE_OMIT_VIEW) */
02044 
02045 #ifndef SQLITE_OMIT_VIEW
02046 /*
02047 ** This routine attempts to flatten subqueries in order to speed
02048 ** execution.  It returns 1 if it makes changes and 0 if no flattening
02049 ** occurs.
02050 **
02051 ** To understand the concept of flattening, consider the following
02052 ** query:
02053 **
02054 **     SELECT a FROM (SELECT x+y AS a FROM t1 WHERE z<100) WHERE a>5
02055 **
02056 ** The default way of implementing this query is to execute the
02057 ** subquery first and store the results in a temporary table, then
02058 ** run the outer query on that temporary table.  This requires two
02059 ** passes over the data.  Furthermore, because the temporary table
02060 ** has no indices, the WHERE clause on the outer query cannot be
02061 ** optimized.
02062 **
02063 ** This routine attempts to rewrite queries such as the above into
02064 ** a single flat select, like this:
02065 **
02066 **     SELECT x+y AS a FROM t1 WHERE z<100 AND a>5
02067 **
02068 ** The code generated for this simpification gives the same result
02069 ** but only has to scan the data once.  And because indices might 
02070 ** exist on the table t1, a complete scan of the data might be
02071 ** avoided.
02072 **
02073 ** Flattening is only attempted if all of the following are true:
02074 **
02075 **   (1)  The subquery and the outer query do not both use aggregates.
02076 **
02077 **   (2)  The subquery is not an aggregate or the outer query is not a join.
02078 **
02079 **   (3)  The subquery is not the right operand of a left outer join, or
02080 **        the subquery is not itself a join.  (Ticket #306)
02081 **
02082 **   (4)  The subquery is not DISTINCT or the outer query is not a join.
02083 **
02084 **   (5)  The subquery is not DISTINCT or the outer query does not use
02085 **        aggregates.
02086 **
02087 **   (6)  The subquery does not use aggregates or the outer query is not
02088 **        DISTINCT.
02089 **
02090 **   (7)  The subquery has a FROM clause.
02091 **
02092 **   (8)  The subquery does not use LIMIT or the outer query is not a join.
02093 **
02094 **   (9)  The subquery does not use LIMIT or the outer query does not use
02095 **        aggregates.
02096 **
02097 **  (10)  The subquery does not use aggregates or the outer query does not
02098 **        use LIMIT.
02099 **
02100 **  (11)  The subquery and the outer query do not both have ORDER BY clauses.
02101 **
02102 **  (12)  The subquery is not the right term of a LEFT OUTER JOIN or the
02103 **        subquery has no WHERE clause.  (added by ticket #350)
02104 **
02105 **  (13)  The subquery and outer query do not both use LIMIT
02106 **
02107 **  (14)  The subquery does not use OFFSET
02108 **
02109 ** In this routine, the "p" parameter is a pointer to the outer query.
02110 ** The subquery is p->pSrc->a[iFrom].  isAgg is true if the outer query
02111 ** uses aggregates and subqueryIsAgg is true if the subquery uses aggregates.
02112 **
02113 ** If flattening is not attempted, this routine is a no-op and returns 0.
02114 ** If flattening is attempted this routine returns 1.
02115 **
02116 ** All of the expression analysis must occur on both the outer query and
02117 ** the subquery before this routine runs.
02118 */
02119 static int flattenSubquery(
02120   Select *p,           /* The parent or outer SELECT statement */
02121   int iFrom,           /* Index in p->pSrc->a[] of the inner subquery */
02122   int isAgg,           /* True if outer SELECT uses aggregate functions */
02123   int subqueryIsAgg    /* True if the subquery uses aggregate functions */
02124 ){
02125   Select *pSub;       /* The inner query or "subquery" */
02126   SrcList *pSrc;      /* The FROM clause of the outer query */
02127   SrcList *pSubSrc;   /* The FROM clause of the subquery */
02128   ExprList *pList;    /* The result set of the outer query */
02129   int iParent;        /* VDBE cursor number of the pSub result set temp table */
02130   int i;              /* Loop counter */
02131   Expr *pWhere;                    /* The WHERE clause */
02132   struct SrcList_item *pSubitem;   /* The subquery */
02133 
02134   /* Check to see if flattening is permitted.  Return 0 if not.
02135   */
02136   if( p==0 ) return 0;
02137   pSrc = p->pSrc;
02138   assert( pSrc && iFrom>=0 && iFrom<pSrc->nSrc );
02139   pSubitem = &pSrc->a[iFrom];
02140   pSub = pSubitem->pSelect;
02141   assert( pSub!=0 );
02142   if( isAgg && subqueryIsAgg ) return 0;                 /* Restriction (1)  */
02143   if( subqueryIsAgg && pSrc->nSrc>1 ) return 0;          /* Restriction (2)  */
02144   pSubSrc = pSub->pSrc;
02145   assert( pSubSrc );
02146   /* Prior to version 3.1.2, when LIMIT and OFFSET had to be simple constants,
02147   ** not arbitrary expresssions, we allowed some combining of LIMIT and OFFSET
02148   ** because they could be computed at compile-time.  But when LIMIT and OFFSET
02149   ** became arbitrary expressions, we were forced to add restrictions (13)
02150   ** and (14). */
02151   if( pSub->pLimit && p->pLimit ) return 0;              /* Restriction (13) */
02152   if( pSub->pOffset ) return 0;                          /* Restriction (14) */
02153   if( pSubSrc->nSrc==0 ) return 0;                       /* Restriction (7)  */
02154   if( (pSub->isDistinct || pSub->pLimit) 
02155          && (pSrc->nSrc>1 || isAgg) ){          /* Restrictions (4)(5)(8)(9) */
02156      return 0;       
02157   }
02158   if( p->isDistinct && subqueryIsAgg ) return 0;         /* Restriction (6)  */
02159   if( (p->disallowOrderBy || p->pOrderBy) && pSub->pOrderBy ){
02160      return 0;                                           /* Restriction (11) */
02161   }
02162 
02163   /* Restriction 3:  If the subquery is a join, make sure the subquery is 
02164   ** not used as the right operand of an outer join.  Examples of why this
02165   ** is not allowed:
02166   **
02167   **         t1 LEFT OUTER JOIN (t2 JOIN t3)
02168   **
02169   ** If we flatten the above, we would get
02170   **
02171   **         (t1 LEFT OUTER JOIN t2) JOIN t3
02172   **
02173   ** which is not at all the same thing.
02174   */
02175   if( pSubSrc->nSrc>1 && iFrom>0 && (pSrc->a[iFrom-1].jointype & JT_OUTER)!=0 ){
02176     return 0;
02177   }
02178 
02179   /* Restriction 12:  If the subquery is the right operand of a left outer
02180   ** join, make sure the subquery has no WHERE clause.
02181   ** An examples of why this is not allowed:
02182   **
02183   **         t1 LEFT OUTER JOIN (SELECT * FROM t2 WHERE t2.x>0)
02184   **
02185   ** If we flatten the above, we would get
02186   **
02187   **         (t1 LEFT OUTER JOIN t2) WHERE t2.x>0
02188   **
02189   ** But the t2.x>0 test will always fail on a NULL row of t2, which
02190   ** effectively converts the OUTER JOIN into an INNER JOIN.
02191   */
02192   if( iFrom>0 && (pSrc->a[iFrom-1].jointype & JT_OUTER)!=0 
02193       && pSub->pWhere!=0 ){
02194     return 0;
02195   }
02196 
02197   /* If we reach this point, it means flattening is permitted for the
02198   ** iFrom-th entry of the FROM clause in the outer query.
02199   */
02200 
02201   /* Move all of the FROM elements of the subquery into the
02202   ** the FROM clause of the outer query.  Before doing this, remember
02203   ** the cursor number for the original outer query FROM element in
02204   ** iParent.  The iParent cursor will never be used.  Subsequent code
02205   ** will scan expressions looking for iParent references and replace
02206   ** those references with expressions that resolve to the subquery FROM
02207   ** elements we are now copying in.
02208   */
02209   iParent = pSubitem->iCursor;
02210   {
02211     int nSubSrc = pSubSrc->nSrc;
02212     int jointype = pSubitem->jointype;
02213 
02214     sqlite3DeleteTable(0, pSubitem->pTab);
02215     sqliteFree(pSubitem->zDatabase);
02216     sqliteFree(pSubitem->zName);
02217     sqliteFree(pSubitem->zAlias);
02218     if( nSubSrc>1 ){
02219       int extra = nSubSrc - 1;
02220       for(i=1; i<nSubSrc; i++){
02221         pSrc = sqlite3SrcListAppend(pSrc, 0, 0);
02222       }
02223       p->pSrc = pSrc;
02224       for(i=pSrc->nSrc-1; i-extra>=iFrom; i--){
02225         pSrc->a[i] = pSrc->a[i-extra];
02226       }
02227     }
02228     for(i=0; i<nSubSrc; i++){
02229       pSrc->a[i+iFrom] = pSubSrc->a[i];
02230       memset(&pSubSrc->a[i], 0, sizeof(pSubSrc->a[i]));
02231     }
02232     pSrc->a[iFrom+nSubSrc-1].jointype = jointype;
02233   }
02234 
02235   /* Now begin substituting subquery result set expressions for 
02236   ** references to the iParent in the outer query.
02237   ** 
02238   ** Example:
02239   **
02240   **   SELECT a+5, b*10 FROM (SELECT x*3 AS a, y+10 AS b FROM t1) WHERE a>b;
02241   **   \                     \_____________ subquery __________/          /
02242   **    \_____________________ outer query ______________________________/
02243   **
02244   ** We look at every expression in the outer query and every place we see
02245   ** "a" we substitute "x*3" and every place we see "b" we substitute "y+10".
02246   */
02247   pList = p->pEList;
02248   for(i=0; i<pList->nExpr; i++){
02249     Expr *pExpr;
02250     if( pList->a[i].zName==0 && (pExpr = pList->a[i].pExpr)->span.z!=0 ){
02251       pList->a[i].zName = sqliteStrNDup((char*)pExpr->span.z, pExpr->span.n);
02252     }
02253   }
02254   substExprList(p->pEList, iParent, pSub->pEList);
02255   if( isAgg ){
02256     substExprList(p->pGroupBy, iParent, pSub->pEList);
02257     substExpr(p->pHaving, iParent, pSub->pEList);
02258   }
02259   if( pSub->pOrderBy ){
02260     assert( p->pOrderBy==0 );
02261     p->pOrderBy = pSub->pOrderBy;
02262     pSub->pOrderBy = 0;
02263   }else if( p->pOrderBy ){
02264     substExprList(p->pOrderBy, iParent, pSub->pEList);
02265   }
02266   if( pSub->pWhere ){
02267     pWhere = sqlite3ExprDup(pSub->pWhere);
02268   }else{
02269     pWhere = 0;
02270   }
02271   if( subqueryIsAgg ){
02272     assert( p->pHaving==0 );
02273     p->pHaving = p->pWhere;
02274     p->pWhere = pWhere;
02275     substExpr(p->pHaving, iParent, pSub->pEList);
02276     p->pHaving = sqlite3ExprAnd(p->pHaving, sqlite3ExprDup(pSub->pHaving));
02277     assert( p->pGroupBy==0 );
02278     p->pGroupBy = sqlite3ExprListDup(pSub->pGroupBy);
02279   }else{
02280     substExpr(p->pWhere, iParent, pSub->pEList);
02281     p->pWhere = sqlite3ExprAnd(p->pWhere, pWhere);
02282   }
02283 
02284   /* The flattened query is distinct if either the inner or the
02285   ** outer query is distinct. 
02286   */
02287   p->isDistinct = p->isDistinct || pSub->isDistinct;
02288 
02289   /*
02290   ** SELECT ... FROM (SELECT ... LIMIT a OFFSET b) LIMIT x OFFSET y;
02291   **
02292   ** One is tempted to try to add a and b to combine the limits.  But this
02293   ** does not work if either limit is negative.
02294   */
02295   if( pSub->pLimit ){
02296     p->pLimit = pSub->pLimit;
02297     pSub->pLimit = 0;
02298   }
02299 
02300   /* Finially, delete what is left of the subquery and return
02301   ** success.
02302   */
02303   sqlite3SelectDelete(pSub);
02304   return 1;
02305 }
02306 #endif /* SQLITE_OMIT_VIEW */
02307 
02308 /*
02309 ** Analyze the SELECT statement passed in as an argument to see if it
02310 ** is a simple min() or max() query.  If it is and this query can be
02311 ** satisfied using a single seek to the beginning or end of an index,
02312 ** then generate the code for this SELECT and return 1.  If this is not a 
02313 ** simple min() or max() query, then return 0;
02314 **
02315 ** A simply min() or max() query looks like this:
02316 **
02317 **    SELECT min(a) FROM table;
02318 **    SELECT max(a) FROM table;
02319 **
02320 ** The query may have only a single table in its FROM argument.  There
02321 ** can be no GROUP BY or HAVING or WHERE clauses.  The result set must
02322 ** be the min() or max() of a single column of the table.  The column
02323 ** in the min() or max() function must be indexed.
02324 **
02325 ** The parameters to this routine are the same as for sqlite3Select().
02326 ** See the header comment on that routine for additional information.
02327 */
02328 static int simpleMinMaxQuery(Parse *pParse, Select *p, int eDest, int iParm){
02329   Expr *pExpr;
02330   int iCol;
02331   Table *pTab;
02332   Index *pIdx;
02333   int base;
02334   Vdbe *v;
02335   int seekOp;
02336   ExprList *pEList, *pList, eList;
02337   struct ExprList_item eListItem;
02338   SrcList *pSrc;
02339   int brk;
02340   int iDb;
02341 
02342   /* Check to see if this query is a simple min() or max() query.  Return
02343   ** zero if it is  not.
02344   */
02345   if( p->pGroupBy || p->pHaving || p->pWhere ) return 0;
02346   pSrc = p->pSrc;
02347   if( pSrc->nSrc!=1 ) return 0;
02348   pEList = p->pEList;
02349   if( pEList->nExpr!=1 ) return 0;
02350   pExpr = pEList->a[0].pExpr;
02351   if( pExpr->op!=TK_AGG_FUNCTION ) return 0;
02352   pList = pExpr->pList;
02353   if( pList==0 || pList->nExpr!=1 ) return 0;
02354   if( pExpr->token.n!=3 ) return 0;
02355   if( sqlite3StrNICmp((char*)pExpr->token.z,"min",3)==0 ){
02356     seekOp = OP_Rewind;
02357   }else if( sqlite3StrNICmp((char*)pExpr->token.z,"max",3)==0 ){
02358     seekOp = OP_Last;
02359   }else{
02360     return 0;
02361   }
02362   pExpr = pList->a[0].pExpr;
02363   if( pExpr->op!=TK_COLUMN ) return 0;
02364   iCol = pExpr->iColumn;
02365   pTab = pSrc->a[0].pTab;
02366 
02367 
02368   /* If we get to here, it means the query is of the correct form.
02369   ** Check to make sure we have an index and make pIdx point to the
02370   ** appropriate index.  If the min() or max() is on an INTEGER PRIMARY
02371   ** key column, no index is necessary so set pIdx to NULL.  If no
02372   ** usable index is found, return 0.
02373   */
02374   if( iCol<0 ){
02375     pIdx = 0;
02376   }else{
02377     CollSeq *pColl = sqlite3ExprCollSeq(pParse, pExpr);
02378     for(pIdx=pTab->pIndex; pIdx; pIdx=pIdx->pNext){
02379       assert( pIdx->nColumn>=1 );
02380       if( pIdx->aiColumn[0]==iCol && 
02381           0==sqlite3StrICmp(pIdx->azColl[0], pColl->zName) ){
02382         break;
02383       }
02384     }
02385     if( pIdx==0 ) return 0;
02386   }
02387 
02388   /* Identify column types if we will be using the callback.  This
02389   ** step is skipped if the output is going to a table or a memory cell.
02390   ** The column names have already been generated in the calling function.
02391   */
02392   v = sqlite3GetVdbe(pParse);
02393   if( v==0 ) return 0;
02394 
02395   /* If the output is destined for a temporary table, open that table.
02396   */
02397   if( eDest==SRT_VirtualTab ){
02398     sqlite3VdbeAddOp(v, OP_OpenVirtual, iParm, 1);
02399   }
02400 
02401   /* Generating code to find the min or the max.  Basically all we have
02402   ** to do is find the first or the last entry in the chosen index.  If
02403   ** the min() or max() is on the INTEGER PRIMARY KEY, then find the first
02404   ** or last entry in the main table.
02405   */
02406   iDb = sqlite3SchemaToIndex(pParse->db, pTab->pSchema);
02407   assert( iDb>=0 || pTab->isTransient );
02408   sqlite3CodeVerifySchema(pParse, iDb);
02409   sqlite3TableLock(pParse, iDb, pTab->tnum, 0, pTab->zName);
02410   base = pSrc->a[0].iCursor;
02411   brk = sqlite3VdbeMakeLabel(v);
02412   computeLimitRegisters(pParse, p, brk);
02413   if( pSrc->a[0].pSelect==0 ){
02414     sqlite3OpenTable(pParse, base, iDb, pTab, OP_OpenRead);
02415   }
02416   if( pIdx==0 ){
02417     sqlite3VdbeAddOp(v, seekOp, base, 0);
02418   }else{
02419     /* Even though the cursor used to open the index here is closed
02420     ** as soon as a single value has been read from it, allocate it
02421     ** using (pParse->nTab++) to prevent the cursor id from being 
02422     ** reused. This is important for statements of the form 
02423     ** "INSERT INTO x SELECT max() FROM x".
02424     */
02425     int iIdx;
02426     KeyInfo *pKey = sqlite3IndexKeyinfo(pParse, pIdx);
02427     iIdx = pParse->nTab++;
02428     assert( pIdx->pSchema==pTab->pSchema );
02429     sqlite3VdbeAddOp(v, OP_Integer, iDb, 0);
02430     sqlite3VdbeOp3(v, OP_OpenRead, iIdx, pIdx->tnum, 
02431         (char*)pKey, P3_KEYINFO_HANDOFF);
02432     if( seekOp==OP_Rewind ){
02433       sqlite3VdbeAddOp(v, OP_Null, 0, 0);
02434       sqlite3VdbeAddOp(v, OP_MakeRecord, 1, 0);
02435       seekOp = OP_MoveGt;
02436     }
02437     sqlite3VdbeAddOp(v, seekOp, iIdx, 0);
02438     sqlite3VdbeAddOp(v, OP_IdxRowid, iIdx, 0);
02439     sqlite3VdbeAddOp(v, OP_Close, iIdx, 0);
02440     sqlite3VdbeAddOp(v, OP_MoveGe, base, 0);
02441   }
02442   eList.nExpr = 1;
02443   memset(&eListItem, 0, sizeof(eListItem));
02444   eList.a = &eListItem;
02445   eList.a[0].pExpr = pExpr;
02446   selectInnerLoop(pParse, p, &eList, 0, 0, 0, -1, eDest, iParm, brk, brk, 0);
02447   sqlite3VdbeResolveLabel(v, brk);
02448   sqlite3VdbeAddOp(v, OP_Close, base, 0);
02449   
02450   return 1;
02451 }
02452 
02453 /*
02454 ** Analyze and ORDER BY or GROUP BY clause in a SELECT statement.  Return
02455 ** the number of errors seen.
02456 **
02457 ** An ORDER BY or GROUP BY is a list of expressions.  If any expression
02458 ** is an integer constant, then that expression is replaced by the
02459 ** corresponding entry in the result set.
02460 */
02461 static int processOrderGroupBy(
02462   NameContext *pNC,     /* Name context of the SELECT statement. */
02463   ExprList *pOrderBy,   /* The ORDER BY or GROUP BY clause to be processed */
02464   const char *zType     /* Either "ORDER" or "GROUP", as appropriate */
02465 ){
02466   int i;
02467   ExprList *pEList = pNC->pEList;     /* The result set of the SELECT */
02468   Parse *pParse = pNC->pParse;     /* The result set of the SELECT */
02469   assert( pEList );
02470 
02471   if( pOrderBy==0 ) return 0;
02472   for(i=0; i<pOrderBy->nExpr; i++){
02473     int iCol;
02474     Expr *pE = pOrderBy->a[i].pExpr;
02475     if( sqlite3ExprIsInteger(pE, &iCol) ){
02476       if( iCol>0 && iCol<=pEList->nExpr ){
02477         sqlite3ExprDelete(pE);
02478         pE = pOrderBy->a[i].pExpr = sqlite3ExprDup(pEList->a[iCol-1].pExpr);
02479       }else{
02480         sqlite3ErrorMsg(pParse, 
02481            "%s BY column number %d out of range - should be "
02482            "between 1 and %d", zType, iCol, pEList->nExpr);
02483         return 1;
02484       }
02485     }
02486     if( sqlite3ExprResolveNames(pNC, pE) ){
02487       return 1;
02488     }
02489   }
02490   return 0;
02491 }
02492 
02493 /*
02494 ** This routine resolves any names used in the result set of the
02495 ** supplied SELECT statement. If the SELECT statement being resolved
02496 ** is a sub-select, then pOuterNC is a pointer to the NameContext 
02497 ** of the parent SELECT.
02498 */
02499 int sqlite3SelectResolve(
02500   Parse *pParse,         /* The parser context */
02501   Select *p,             /* The SELECT statement being coded. */
02502   NameContext *pOuterNC  /* The outer name context. May be NULL. */
02503 ){
02504   ExprList *pEList;          /* Result set. */
02505   int i;                     /* For-loop variable used in multiple places */
02506   NameContext sNC;           /* Local name-context */
02507   ExprList *pGroupBy;        /* The group by clause */
02508 
02509   /* If this routine has run before, return immediately. */
02510   if( p->isResolved ){
02511     assert( !pOuterNC );
02512     return SQLITE_OK;
02513   }
02514   p->isResolved = 1;
02515 
02516   /* If there have already been errors, do nothing. */
02517   if( pParse->nErr>0 ){
02518     return SQLITE_ERROR;
02519   }
02520 
02521   /* Prepare the select statement. This call will allocate all cursors
02522   ** required to handle the tables and subqueries in the FROM clause.
02523   */
02524   if( prepSelectStmt(pParse, p) ){
02525     return SQLITE_ERROR;
02526   }
02527 
02528   /* Resolve the expressions in the LIMIT and OFFSET clauses. These
02529   ** are not allowed to refer to any names, so pass an empty NameContext.
02530   */
02531   memset(&sNC, 0, sizeof(sNC));
02532   sNC.pParse = pParse;
02533   if( sqlite3ExprResolveNames(&sNC, p->pLimit) ||
02534       sqlite3ExprResolveNames(&sNC, p->pOffset) ){
02535     return SQLITE_ERROR;
02536   }
02537 
02538   /* Set up the local name-context to pass to ExprResolveNames() to
02539   ** resolve the expression-list.
02540   */
02541   sNC.allowAgg = 1;
02542   sNC.pSrcList = p->pSrc;
02543   sNC.pNext = pOuterNC;
02544 
02545   /* Resolve names in the result set. */
02546   pEList = p->pEList;
02547   if( !pEList ) return SQLITE_ERROR;
02548   for(i=0; i<pEList->nExpr; i++){
02549     Expr *pX = pEList->a[i].pExpr;
02550     if( sqlite3ExprResolveNames(&sNC, pX) ){
02551       return SQLITE_ERROR;
02552     }
02553   }
02554 
02555   /* If there are no aggregate functions in the result-set, and no GROUP BY 
02556   ** expression, do not allow aggregates in any of the other expressions.
02557   */
02558   assert( !p->isAgg );
02559   pGroupBy = p->pGroupBy;
02560   if( pGroupBy || sNC.hasAgg ){
02561     p->isAgg = 1;
02562   }else{
02563     sNC.allowAgg = 0;
02564   }
02565 
02566   /* If a HAVING clause is present, then there must be a GROUP BY clause.
02567   */
02568   if( p->pHaving && !pGroupBy ){
02569     sqlite3ErrorMsg(pParse, "a GROUP BY clause is required before HAVING");
02570     return SQLITE_ERROR;
02571   }
02572 
02573   /* Add the expression list to the name-context before parsing the
02574   ** other expressions in the SELECT statement. This is so that
02575   ** expressions in the WHERE clause (etc.) can refer to expressions by
02576   ** aliases in the result set.
02577   **
02578   ** Minor point: If this is the case, then the expression will be
02579   ** re-evaluated for each reference to it.
02580   */
02581   sNC.pEList = p->pEList;
02582   if( sqlite3ExprResolveNames(&sNC, p->pWhere) ||
02583       sqlite3ExprResolveNames(&sNC, p->pHaving) ||
02584       processOrderGroupBy(&sNC, p->pOrderBy, "ORDER") ||
02585       processOrderGroupBy(&sNC, pGroupBy, "GROUP")
02586   ){
02587     return SQLITE_ERROR;
02588   }
02589 
02590   /* Make sure the GROUP BY clause does not contain aggregate functions.
02591   */
02592   if( pGroupBy ){
02593     struct ExprList_item *pItem;
02594   
02595     for(i=0, pItem=pGroupBy->a; i<pGroupBy->nExpr; i++, pItem++){
02596       if( ExprHasProperty(pItem->pExpr, EP_Agg) ){
02597         sqlite3ErrorMsg(pParse, "aggregate functions are not allowed in "
02598             "the GROUP BY clause");
02599         return SQLITE_ERROR;
02600       }
02601     }
02602   }
02603 
02604   return SQLITE_OK;
02605 }
02606 
02607 /*
02608 ** Reset the aggregate accumulator.
02609 **
02610 ** The aggregate accumulator is a set of memory cells that hold
02611 ** intermediate results while calculating an aggregate.  This
02612 ** routine simply stores NULLs in all of those memory cells.
02613 */
02614 static void resetAccumulator(Parse *pParse, AggInfo *pAggInfo){
02615   Vdbe *v = pParse->pVdbe;
02616   int i;
02617   struct AggInfo_func *pFunc;
02618   if( pAggInfo->nFunc+pAggInfo->nColumn==0 ){
02619     return;
02620   }
02621   for(i=0; i<pAggInfo->nColumn; i++){
02622     sqlite3VdbeAddOp(v, OP_MemNull, pAggInfo->aCol[i].iMem, 0);
02623   }
02624   for(pFunc=pAggInfo->aFunc, i=0; i<pAggInfo->nFunc; i++, pFunc++){
02625     sqlite3VdbeAddOp(v, OP_MemNull, pFunc->iMem, 0);
02626     if( pFunc->iDistinct>=0 ){
02627       Expr *pE = pFunc->pExpr;
02628       if( pE->pList==0 || pE->pList->nExpr!=1 ){
02629         sqlite3ErrorMsg(pParse, "DISTINCT in aggregate must be followed "
02630            "by an expression");
02631         pFunc->iDistinct = -1;
02632       }else{
02633         KeyInfo *pKeyInfo = keyInfoFromExprList(pParse, pE->pList);
02634         sqlite3VdbeOp3(v, OP_OpenVirtual, pFunc->iDistinct, 0, 
02635                           (char*)pKeyInfo, P3_KEYINFO_HANDOFF);
02636       }
02637     }
02638   }
02639 }
02640 
02641 /*
02642 ** Invoke the OP_AggFinalize opcode for every aggregate function
02643 ** in the AggInfo structure.
02644 */
02645 static void finalizeAggFunctions(Parse *pParse, AggInfo *pAggInfo){
02646   Vdbe *v = pParse->pVdbe;
02647   int i;
02648   struct AggInfo_func *pF;
02649   for(i=0, pF=pAggInfo->aFunc; i<pAggInfo->nFunc; i++, pF++){
02650     ExprList *pList = pF->pExpr->pList;
02651     sqlite3VdbeOp3(v, OP_AggFinal, pF->iMem, pList ? pList->nExpr : 0,
02652                       (void*)pF->pFunc, P3_FUNCDEF);
02653   }
02654 }
02655 
02656 /*
02657 ** Update the accumulator memory cells for an aggregate based on
02658 ** the current cursor position.
02659 */
02660 static void updateAccumulator(Parse *pParse, AggInfo *pAggInfo){
02661   Vdbe *v = pParse->pVdbe;
02662   int i;
02663   struct AggInfo_func *pF;
02664   struct AggInfo_col *pC;
02665 
02666   pAggInfo->directMode = 1;
02667   for(i=0, pF=pAggInfo->aFunc; i<pAggInfo->nFunc; i++, pF++){
02668     int nArg;
02669     int addrNext = 0;
02670     ExprList *pList = pF->pExpr->pList;
02671     if( pList ){
02672       nArg = pList->nExpr;
02673       sqlite3ExprCodeExprList(pParse, pList);
02674     }else{
02675       nArg = 0;
02676     }
02677     if( pF->iDistinct>=0 ){
02678       addrNext = sqlite3VdbeMakeLabel(v);
02679       assert( nArg==1 );
02680       codeDistinct(v, pF->iDistinct, addrNext, 1);
02681     }
02682     if( pF->pFunc->needCollSeq ){
02683       CollSeq *pColl = 0;
02684       struct ExprList_item *pItem;
02685       int j;
02686       assert( pList!=0 );  /* pList!=0 if pF->pFunc->needCollSeq is true */
02687       for(j=0, pItem=pList->a; !pColl && j<nArg; j++, pItem++){
02688         pColl = sqlite3ExprCollSeq(pParse, pItem->pExpr);
02689       }
02690       if( !pColl ){
02691         pColl = pParse->db->pDfltColl;
02692       }
02693       sqlite3VdbeOp3(v, OP_CollSeq, 0, 0, (char *)pColl, P3_COLLSEQ);
02694     }
02695     sqlite3VdbeOp3(v, OP_AggStep, pF->iMem, nArg, (void*)pF->pFunc, P3_FUNCDEF);
02696     if( addrNext ){
02697       sqlite3VdbeResolveLabel(v, addrNext);
02698     }
02699   }
02700   for(i=0, pC=pAggInfo->aCol; i<pAggInfo->nAccumulator; i++, pC++){
02701     sqlite3ExprCode(pParse, pC->pExpr);
02702     sqlite3VdbeAddOp(v, OP_MemStore, pC->iMem, 1);
02703   }
02704   pAggInfo->directMode = 0;
02705 }
02706 
02707 
02708 /*
02709 ** Generate code for the given SELECT statement.
02710 **
02711 ** The results are distributed in various ways depending on the
02712 ** value of eDest and iParm.
02713 **
02714 **     eDest Value       Result
02715 **     ------------    -------------------------------------------
02716 **     SRT_Callback    Invoke the callback for each row of the result.
02717 **
02718 **     SRT_Mem         Store first result in memory cell iParm
02719 **
02720 **     SRT_Set         Store results as keys of table iParm.
02721 **
02722 **     SRT_Union       Store results as a key in a temporary table iParm
02723 **
02724 **     SRT_Except      Remove results from the temporary table iParm.
02725 **
02726 **     SRT_Table       Store results in temporary table iParm
02727 **
02728 ** The table above is incomplete.  Additional eDist value have be added
02729 ** since this comment was written.  See the selectInnerLoop() function for
02730 ** a complete listing of the allowed values of eDest and their meanings.
02731 **
02732 ** This routine returns the number of errors.  If any errors are
02733 ** encountered, then an appropriate error message is left in
02734 ** pParse->zErrMsg.
02735 **
02736 ** This routine does NOT free the Select structure passed in.  The
02737 ** calling function needs to do that.
02738 **
02739 ** The pParent, parentTab, and *pParentAgg fields are filled in if this
02740 ** SELECT is a subquery.  This routine may try to combine this SELECT
02741 ** with its parent to form a single flat query.  In so doing, it might
02742 ** change the parent query from a non-aggregate to an aggregate query.
02743 ** For that reason, the pParentAgg flag is passed as a pointer, so it
02744 ** can be changed.
02745 **
02746 ** Example 1:   The meaning of the pParent parameter.
02747 **
02748 **    SELECT * FROM t1 JOIN (SELECT x, count(*) FROM t2) JOIN t3;
02749 **    \                      \_______ subquery _______/        /
02750 **     \                                                      /
02751 **      \____________________ outer query ___________________/
02752 **
02753 ** This routine is called for the outer query first.   For that call,
02754 ** pParent will be NULL.  During the processing of the outer query, this 
02755 ** routine is called recursively to handle the subquery.  For the recursive
02756 ** call, pParent will point to the outer query.  Because the subquery is
02757 ** the second element in a three-way join, the parentTab parameter will
02758 ** be 1 (the 2nd value of a 0-indexed array.)
02759 */
02760 int sqlite3Select(
02761   Parse *pParse,         /* The parser context */
02762   Select *p,             /* The SELECT statement being coded. */
02763   int eDest,             /* How to dispose of the results */
02764   int iParm,             /* A parameter used by the eDest disposal method */
02765   Select *pParent,       /* Another SELECT for which this is a sub-query */
02766   int parentTab,         /* Index in pParent->pSrc of this query */
02767   int *pParentAgg,       /* True if pParent uses aggregate functions */
02768   char *aff              /* If eDest is SRT_Union, the affinity string */
02769 ){
02770   int i, j;              /* Loop counters */
02771   WhereInfo *pWInfo;     /* Return from sqlite3WhereBegin() */
02772   Vdbe *v;               /* The virtual machine under construction */
02773   int isAgg;             /* True for select lists like "count(*)" */
02774   ExprList *pEList;      /* List of columns to extract. */
02775   SrcList *pTabList;     /* List of tables to select from */
02776   Expr *pWhere;          /* The WHERE clause.  May be NULL */
02777   ExprList *pOrderBy;    /* The ORDER BY clause.  May be NULL */
02778   ExprList *pGroupBy;    /* The GROUP BY clause.  May be NULL */
02779   Expr *pHaving;         /* The HAVING clause.  May be NULL */
02780   int isDistinct;        /* True if the DISTINCT keyword is present */
02781   int distinct;          /* Table to use for the distinct set */
02782   int rc = 1;            /* Value to return from this function */
02783   int addrSortIndex;     /* Address of an OP_OpenVirtual instruction */
02784   AggInfo sAggInfo;      /* Information used by aggregate queries */
02785   int iEnd;              /* Address of the end of the query */
02786 
02787   if( p==0 || sqlite3MallocFailed() || pParse->nErr ){
02788     return 1;
02789   }
02790   if( sqlite3AuthCheck(pParse, SQLITE_SELECT, 0, 0, 0) ) return 1;
02791   memset(&sAggInfo, 0, sizeof(sAggInfo));
02792 
02793 #ifndef SQLITE_OMIT_COMPOUND_SELECT
02794   /* If there is are a sequence of queries, do the earlier ones first.
02795   */
02796   if( p->pPrior ){
02797     if( p->pRightmost==0 ){
02798       Select *pLoop;
02799       for(pLoop=p; pLoop; pLoop=pLoop->pPrior){
02800         pLoop->pRightmost = p;
02801       }
02802     }
02803     return multiSelect(pParse, p, eDest, iParm, aff);
02804   }
02805 #endif
02806 
02807   pOrderBy = p->pOrderBy;
02808   if( IgnorableOrderby(eDest) ){
02809     p->pOrderBy = 0;
02810   }
02811   if( sqlite3SelectResolve(pParse, p, 0) ){
02812     goto select_end;
02813   }
02814   p->pOrderBy = pOrderBy;
02815 
02816   /* Make local copies of the parameters for this query.
02817   */
02818   pTabList = p->pSrc;
02819   pWhere = p->pWhere;
02820   pGroupBy = p->pGroupBy;
02821   pHaving = p->pHaving;
02822   isAgg = p->isAgg;
02823   isDistinct = p->isDistinct;
02824   pEList = p->pEList;
02825   if( pEList==0 ) goto select_end;
02826 
02827   /* 
02828   ** Do not even attempt to generate any code if we have already seen
02829   ** errors before this routine starts.
02830   */
02831   if( pParse->nErr>0 ) goto select_end;
02832 
02833   /* If writing to memory or generating a set
02834   ** only a single column may be output.
02835   */
02836 #ifndef SQLITE_OMIT_SUBQUERY
02837   if( (eDest==SRT_Mem || eDest==SRT_Set) && pEList->nExpr>1 ){
02838     sqlite3ErrorMsg(pParse, "only a single result allowed for "
02839        "a SELECT that is part of an expression");
02840     goto select_end;
02841   }
02842 #endif
02843 
02844   /* ORDER BY is ignored for some destinations.
02845   */
02846   if( IgnorableOrderby(eDest) ){
02847     pOrderBy = 0;
02848   }
02849 
02850   /* Begin generating code.
02851   */
02852   v = sqlite3GetVdbe(pParse);
02853   if( v==0 ) goto select_end;
02854 
02855   /* Generate code for all sub-queries in the FROM clause
02856   */
02857 #if !defined(SQLITE_OMIT_SUBQUERY) || !defined(SQLITE_OMIT_VIEW)
02858   for(i=0; i<pTabList->nSrc; i++){
02859     const char *zSavedAuthContext = 0;
02860     int needRestoreContext;
02861     struct SrcList_item *pItem = &pTabList->a[i];
02862 
02863     if( pItem->pSelect==0 || pItem->isPopulated ) continue;
02864     if( pItem->zName!=0 ){
02865       zSavedAuthContext = pParse->zAuthContext;
02866       pParse->zAuthContext = pItem->zName;
02867       needRestoreContext = 1;
02868     }else{
02869       needRestoreContext = 0;
02870     }
02871     sqlite3Select(pParse, pItem->pSelect, SRT_VirtualTab, 
02872                  pItem->iCursor, p, i, &isAgg, 0);
02873     if( needRestoreContext ){
02874       pParse->zAuthContext = zSavedAuthContext;
02875     }
02876     pTabList = p->pSrc;
02877     pWhere = p->pWhere;
02878     if( !IgnorableOrderby(eDest) ){
02879       pOrderBy = p->pOrderBy;
02880     }
02881     pGroupBy = p->pGroupBy;
02882     pHaving = p->pHaving;
02883     isDistinct = p->isDistinct;
02884   }
02885 #endif
02886 
02887   /* Check for the special case of a min() or max() function by itself
02888   ** in the result set.
02889   */
02890   if( simpleMinMaxQuery(pParse, p, eDest, iParm) ){
02891     rc = 0;
02892     goto select_end;
02893   }
02894 
02895   /* Check to see if this is a subquery that can be "flattened" into its parent.
02896   ** If flattening is a possiblity, do so and return immediately.  
02897   */
02898 #ifndef SQLITE_OMIT_VIEW
02899   if( pParent && pParentAgg &&
02900       flattenSubquery(pParent, parentTab, *pParentAgg, isAgg) ){
02901     if( isAgg ) *pParentAgg = 1;
02902     goto select_end;
02903   }
02904 #endif
02905 
02906   /* If there is an ORDER BY clause, resolve any collation sequences
02907   ** names that have been explicitly specified and create a sorting index.
02908   **
02909   ** This sorting index might end up being unused if the data can be 
02910   ** extracted in pre-sorted order.  If that is the case, then the
02911   ** OP_OpenVirtual instruction will be changed to an OP_Noop once
02912   ** we figure out that the sorting index is not needed.  The addrSortIndex
02913   ** variable is used to facilitate that change.
02914   */
02915   if( pOrderBy ){
02916     struct ExprList_item *pTerm;
02917     KeyInfo *pKeyInfo;
02918     for(i=0, pTerm=pOrderBy->a; i<pOrderBy->nExpr; i++, pTerm++){
02919       if( pTerm->zName ){
02920         pTerm->pExpr->pColl = sqlite3LocateCollSeq(pParse, pTerm->zName, -1);
02921       }
02922     }
02923     if( pParse->nErr ){
02924       goto select_end;
02925     }
02926     pKeyInfo = keyInfoFromExprList(pParse, pOrderBy);
02927     pOrderBy->iECursor = pParse->nTab++;
02928     p->addrOpenVirt[2] = addrSortIndex =
02929        sqlite3VdbeOp3(v, OP_OpenVirtual, pOrderBy->iECursor, pOrderBy->nExpr+2, 
02930                         (char*)pKeyInfo, P3_KEYINFO_HANDOFF);
02931   }else{
02932     addrSortIndex = -1;
02933   }
02934 
02935   /* If the output is destined for a temporary table, open that table.
02936   */
02937   if( eDest==SRT_VirtualTab ){
02938     sqlite3VdbeAddOp(v, OP_OpenVirtual, iParm, pEList->nExpr);
02939   }
02940 
02941   /* Set the limiter.
02942   */
02943   iEnd = sqlite3VdbeMakeLabel(v);
02944   computeLimitRegisters(pParse, p, iEnd);
02945 
02946   /* Open a virtual index to use for the distinct set.
02947   */
02948   if( isDistinct ){
02949     KeyInfo *pKeyInfo;
02950     distinct = pParse->nTab++;
02951     pKeyInfo = keyInfoFromExprList(pParse, p->pEList);
02952     sqlite3VdbeOp3(v, OP_OpenVirtual, distinct, 0, 
02953                         (char*)pKeyInfo, P3_KEYINFO_HANDOFF);
02954   }else{
02955     distinct = -1;
02956   }
02957 
02958   /* Aggregate and non-aggregate queries are handled differently */
02959   if( !isAgg && pGroupBy==0 ){
02960     /* This case is for non-aggregate queries
02961     ** Begin the database scan
02962     */
02963     pWInfo = sqlite3WhereBegin(pParse, pTabList, pWhere, &pOrderBy);
02964     if( pWInfo==0 ) goto select_end;
02965 
02966     /* If sorting index that was created by a prior OP_OpenVirtual 
02967     ** instruction ended up not being needed, then change the OP_OpenVirtual
02968     ** into an OP_Noop.
02969     */
02970     if( addrSortIndex>=0 && pOrderBy==0 ){
02971       sqlite3VdbeChangeToNoop(v, addrSortIndex, 1);
02972       p->addrOpenVirt[2] = -1;
02973     }
02974 
02975     /* Use the standard inner loop
02976     */
02977     if( selectInnerLoop(pParse, p, pEList, 0, 0, pOrderBy, distinct, eDest,
02978                     iParm, pWInfo->iContinue, pWInfo->iBreak, aff) ){
02979        goto select_end;
02980     }
02981 
02982     /* End the database scan loop.
02983     */
02984     sqlite3WhereEnd(pWInfo);
02985   }else{
02986     /* This is the processing for aggregate queries */
02987     NameContext sNC;    /* Name context for processing aggregate information */
02988     int iAMem;          /* First Mem address for storing current GROUP BY */
02989     int iBMem;          /* First Mem address for previous GROUP BY */
02990     int iUseFlag;       /* Mem address holding flag indicating that at least
02991                         ** one row of the input to the aggregator has been
02992                         ** processed */
02993     int iAbortFlag;     /* Mem address which causes query abort if positive */
02994     int groupBySort;    /* Rows come from source in GROUP BY order */
02995 
02996 
02997     /* The following variables hold addresses or labels for parts of the
02998     ** virtual machine program we are putting together */
02999     int addrOutputRow;      /* Start of subroutine that outputs a result row */
03000     int addrSetAbort;       /* Set the abort flag and return */
03001     int addrInitializeLoop; /* Start of code that initializes the input loop */
03002     int addrTopOfLoop;      /* Top of the input loop */
03003     int addrGroupByChange;  /* Code that runs when any GROUP BY term changes */
03004     int addrProcessRow;     /* Code to process a single input row */
03005     int addrEnd;            /* End of all processing */
03006     int addrSortingIdx;     /* The OP_OpenVirtual for the sorting index */
03007     int addrReset;          /* Subroutine for resetting the accumulator */
03008 
03009     addrEnd = sqlite3VdbeMakeLabel(v);
03010 
03011     /* Convert TK_COLUMN nodes into TK_AGG_COLUMN and make entries in
03012     ** sAggInfo for all TK_AGG_FUNCTION nodes in expressions of the
03013     ** SELECT statement.
03014     */
03015     memset(&sNC, 0, sizeof(sNC));
03016     sNC.pParse = pParse;
03017     sNC.pSrcList = pTabList;
03018     sNC.pAggInfo = &sAggInfo;
03019     sAggInfo.nSortingColumn = pGroupBy ? pGroupBy->nExpr+1 : 0;
03020     sAggInfo.pGroupBy = pGroupBy;
03021     if( sqlite3ExprAnalyzeAggList(&sNC, pEList) ){
03022       goto select_end;
03023     }
03024     if( sqlite3ExprAnalyzeAggList(&sNC, pOrderBy) ){
03025       goto select_end;
03026     }
03027     if( pHaving && sqlite3ExprAnalyzeAggregates(&sNC, pHaving) ){
03028       goto select_end;
03029     }
03030     sAggInfo.nAccumulator = sAggInfo.nColumn;
03031     for(i=0; i<sAggInfo.nFunc; i++){
03032       if( sqlite3ExprAnalyzeAggList(&sNC, sAggInfo.aFunc[i].pExpr->pList) ){
03033         goto select_end;
03034       }
03035     }
03036     if( sqlite3MallocFailed() ) goto select_end;
03037 
03038     /* Processing for aggregates with GROUP BY is very different and
03039     ** much more complex tha aggregates without a GROUP BY.
03040     */
03041     if( pGroupBy ){
03042       KeyInfo *pKeyInfo;  /* Keying information for the group by clause */
03043 
03044       /* Create labels that we will be needing
03045       */
03046      
03047       addrInitializeLoop = sqlite3VdbeMakeLabel(v);
03048       addrGroupByChange = sqlite3VdbeMakeLabel(v);
03049       addrProcessRow = sqlite3VdbeMakeLabel(v);
03050 
03051       /* If there is a GROUP BY clause we might need a sorting index to
03052       ** implement it.  Allocate that sorting index now.  If it turns out
03053       ** that we do not need it after all, the OpenVirtual instruction
03054       ** will be converted into a Noop.  
03055       */
03056       sAggInfo.sortingIdx = pParse->nTab++;
03057       pKeyInfo = keyInfoFromExprList(pParse, pGroupBy);
03058       addrSortingIdx =
03059           sqlite3VdbeOp3(v, OP_OpenVirtual, sAggInfo.sortingIdx,
03060                          sAggInfo.nSortingColumn,
03061                          (char*)pKeyInfo, P3_KEYINFO_HANDOFF);
03062 
03063       /* Initialize memory locations used by GROUP BY aggregate processing
03064       */
03065       iUseFlag = pParse->nMem++;
03066       iAbortFlag = pParse->nMem++;
03067       iAMem = pParse->nMem;
03068       pParse->nMem += pGroupBy->nExpr;
03069       iBMem = pParse->nMem;
03070       pParse->nMem += pGroupBy->nExpr;
03071       sqlite3VdbeAddOp(v, OP_MemInt, 0, iAbortFlag);
03072       VdbeComment((v, "# clear abort flag"));
03073       sqlite3VdbeAddOp(v, OP_MemInt, 0, iUseFlag);
03074       VdbeComment((v, "# indicate accumulator empty"));
03075       sqlite3VdbeAddOp(v, OP_Goto, 0, addrInitializeLoop);
03076 
03077       /* Generate a subroutine that outputs a single row of the result
03078       ** set.  This subroutine first looks at the iUseFlag.  If iUseFlag
03079       ** is less than or equal to zero, the subroutine is a no-op.  If
03080       ** the processing calls for the query to abort, this subroutine
03081       ** increments the iAbortFlag memory location before returning in
03082       ** order to signal the caller to abort.
03083       */
03084       addrSetAbort = sqlite3VdbeCurrentAddr(v);
03085       sqlite3VdbeAddOp(v, OP_MemInt, 1, iAbortFlag);
03086       VdbeComment((v, "# set abort flag"));
03087       sqlite3VdbeAddOp(v, OP_Return, 0, 0);
03088       addrOutputRow = sqlite3VdbeCurrentAddr(v);
03089       sqlite3VdbeAddOp(v, OP_IfMemPos, iUseFlag, addrOutputRow+2);
03090       VdbeComment((v, "# Groupby result generator entry point"));
03091       sqlite3VdbeAddOp(v, OP_Return, 0, 0);
03092       finalizeAggFunctions(pParse, &sAggInfo);
03093       if( pHaving ){
03094         sqlite3ExprIfFalse(pParse, pHaving, addrOutputRow+1, 1);
03095       }
03096       rc = selectInnerLoop(pParse, p, p->pEList, 0, 0, pOrderBy,
03097                            distinct, eDest, iParm, 
03098                            addrOutputRow+1, addrSetAbort, aff);
03099       if( rc ){
03100         goto select_end;
03101       }
03102       sqlite3VdbeAddOp(v, OP_Return, 0, 0);
03103       VdbeComment((v, "# end groupby result generator"));
03104 
03105       /* Generate a subroutine that will reset the group-by accumulator
03106       */
03107       addrReset = sqlite3VdbeCurrentAddr(v);
03108       resetAccumulator(pParse, &sAggInfo);
03109       sqlite3VdbeAddOp(v, OP_Return, 0, 0);
03110 
03111       /* Begin a loop that will extract all source rows in GROUP BY order.
03112       ** This might involve two separate loops with an OP_Sort in between, or
03113       ** it might be a single loop that uses an index to extract information
03114       ** in the right order to begin with.
03115       */
03116       sqlite3VdbeResolveLabel(v, addrInitializeLoop);
03117       sqlite3VdbeAddOp(v, OP_Gosub, 0, addrReset);
03118       pWInfo = sqlite3WhereBegin(pParse, pTabList, pWhere, &pGroupBy);
03119       if( pWInfo==0 ) goto select_end;
03120       if( pGroupBy==0 ){
03121         /* The optimizer is able to deliver rows in group by order so
03122         ** we do not have to sort.  The OP_OpenVirtual table will be
03123         ** cancelled later because we still need to use the pKeyInfo
03124         */
03125         pGroupBy = p->pGroupBy;
03126         groupBySort = 0;
03127       }else{
03128         /* Rows are coming out in undetermined order.  We have to push
03129         ** each row into a sorting index, terminate the first loop,
03130         ** then loop over the sorting index in order to get the output
03131         ** in sorted order
03132         */
03133         groupBySort = 1;
03134         sqlite3ExprCodeExprList(pParse, pGroupBy);
03135         sqlite3VdbeAddOp(v, OP_Sequence, sAggInfo.sortingIdx, 0);
03136         j = pGroupBy->nExpr+1;
03137         for(i=0; i<sAggInfo.nColumn; i++){
03138           struct AggInfo_col *pCol = &sAggInfo.aCol[i];
03139           if( pCol->iSorterColumn<j ) continue;
03140           if( pCol->iColumn<0 ){
03141             sqlite3VdbeAddOp(v, OP_Rowid, pCol->iTable, 0);
03142           }else{
03143             sqlite3VdbeAddOp(v, OP_Column, pCol->iTable, pCol->iColumn);
03144           }
03145           j++;
03146         }
03147         sqlite3VdbeAddOp(v, OP_MakeRecord, j, 0);
03148         sqlite3VdbeAddOp(v, OP_IdxInsert, sAggInfo.sortingIdx, 0);
03149         sqlite3WhereEnd(pWInfo);
03150         sqlite3VdbeAddOp(v, OP_Sort, sAggInfo.sortingIdx, addrEnd);
03151         VdbeComment((v, "# GROUP BY sort"));
03152         sAggInfo.useSortingIdx = 1;
03153       }
03154 
03155       /* Evaluate the current GROUP BY terms and store in b0, b1, b2...
03156       ** (b0 is memory location iBMem+0, b1 is iBMem+1, and so forth)
03157       ** Then compare the current GROUP BY terms against the GROUP BY terms
03158       ** from the previous row currently stored in a0, a1, a2...
03159       */
03160       addrTopOfLoop = sqlite3VdbeCurrentAddr(v);
03161       for(j=0; j<pGroupBy->nExpr; j++){
03162         if( groupBySort ){
03163           sqlite3VdbeAddOp(v, OP_Column, sAggInfo.sortingIdx, j);
03164         }else{
03165           sAggInfo.directMode = 1;
03166           sqlite3ExprCode(pParse, pGroupBy->a[j].pExpr);
03167         }
03168         sqlite3VdbeAddOp(v, OP_MemStore, iBMem+j, j<pGroupBy->nExpr-1);
03169       }
03170       for(j=pGroupBy->nExpr-1; j>=0; j--){
03171         if( j<pGroupBy->nExpr-1 ){
03172           sqlite3VdbeAddOp(v, OP_MemLoad, iBMem+j, 0);
03173         }
03174         sqlite3VdbeAddOp(v, OP_MemLoad, iAMem+j, 0);
03175         if( j==0 ){
03176           sqlite3VdbeAddOp(v, OP_Eq, 0x200, addrProcessRow);
03177         }else{
03178           sqlite3VdbeAddOp(v, OP_Ne, 0x200, addrGroupByChange);
03179         }
03180         sqlite3VdbeChangeP3(v, -1, (void*)pKeyInfo->aColl[j], P3_COLLSEQ);
03181       }
03182 
03183       /* Generate code that runs whenever the GROUP BY changes.
03184       ** Change in the GROUP BY are detected by the previous code
03185       ** block.  If there were no changes, this block is skipped.
03186       **
03187       ** This code copies current group by terms in b0,b1,b2,...
03188       ** over to a0,a1,a2.  It then calls the output subroutine
03189       ** and resets the aggregate accumulator registers in preparation
03190       ** for the next GROUP BY batch.
03191       */
03192       sqlite3VdbeResolveLabel(v, addrGroupByChange);
03193       for(j=0; j<pGroupBy->nExpr; j++){
03194         sqlite3VdbeAddOp(v, OP_MemMove, iAMem+j, iBMem+j);
03195       }
03196       sqlite3VdbeAddOp(v, OP_Gosub, 0, addrOutputRow);
03197       VdbeComment((v, "# output one row"));
03198       sqlite3VdbeAddOp(v, OP_IfMemPos, iAbortFlag, addrEnd);
03199       VdbeComment((v, "# check abort flag"));
03200       sqlite3VdbeAddOp(v, OP_Gosub, 0, addrReset);
03201       VdbeComment((v, "# reset accumulator"));
03202 
03203       /* Update the aggregate accumulators based on the content of
03204       ** the current row
03205       */
03206       sqlite3VdbeResolveLabel(v, addrProcessRow);
03207       updateAccumulator(pParse, &sAggInfo);
03208       sqlite3VdbeAddOp(v, OP_MemInt, 1, iUseFlag);
03209       VdbeComment((v, "# indicate data in accumulator"));
03210 
03211       /* End of the loop
03212       */
03213       if( groupBySort ){
03214         sqlite3VdbeAddOp(v, OP_Next, sAggInfo.sortingIdx, addrTopOfLoop);
03215       }else{
03216         sqlite3WhereEnd(pWInfo);
03217         sqlite3VdbeChangeToNoop(v, addrSortingIdx, 1);
03218       }
03219 
03220       /* Output the final row of result
03221       */
03222       sqlite3VdbeAddOp(v, OP_Gosub, 0, addrOutputRow);
03223       VdbeComment((v, "# output final row"));
03224       
03225     } /* endif pGroupBy */
03226     else {
03227       /* This case runs if the aggregate has no GROUP BY clause.  The
03228       ** processing is much simpler since there is only a single row
03229       ** of output.
03230       */
03231       resetAccumulator(pParse, &sAggInfo);
03232       pWInfo = sqlite3WhereBegin(pParse, pTabList, pWhere, 0);
03233       if( pWInfo==0 ) goto select_end;
03234       updateAccumulator(pParse, &sAggInfo);
03235       sqlite3WhereEnd(pWInfo);
03236       finalizeAggFunctions(pParse, &sAggInfo);
03237       pOrderBy = 0;
03238       if( pHaving ){
03239         sqlite3ExprIfFalse(pParse, pHaving, addrEnd, 1);
03240       }
03241       selectInnerLoop(pParse, p, p->pEList, 0, 0, 0, -1, 
03242                       eDest, iParm, addrEnd, addrEnd, aff);
03243     }
03244     sqlite3VdbeResolveLabel(v, addrEnd);
03245     
03246   } /* endif aggregate query */
03247 
03248   /* If there is an ORDER BY clause, then we need to sort the results
03249   ** and send them to the callback one by one.
03250   */
03251   if( pOrderBy ){
03252     generateSortTail(pParse, p, v, pEList->nExpr, eDest, iParm);
03253   }
03254 
03255 #ifndef SQLITE_OMIT_SUBQUERY
03256   /* If this was a subquery, we have now converted the subquery into a
03257   ** temporary table.  So set the SrcList_item.isPopulated flag to prevent
03258   ** this subquery from being evaluated again and to force the use of
03259   ** the temporary table.
03260   */
03261   if( pParent ){
03262     assert( pParent->pSrc->nSrc>parentTab );
03263     assert( pParent->pSrc->a[parentTab].pSelect==p );
03264     pParent->pSrc->a[parentTab].isPopulated = 1;
03265   }
03266 #endif
03267 
03268   /* Jump here to skip this query
03269   */
03270   sqlite3VdbeResolveLabel(v, iEnd);
03271 
03272   /* The SELECT was successfully coded.   Set the return code to 0
03273   ** to indicate no errors.
03274   */
03275   rc = 0;
03276 
03277   /* Control jumps to here if an error is encountered above, or upon
03278   ** successful coding of the SELECT.
03279   */
03280 select_end:
03281 
03282   /* Identify column names if we will be using them in a callback.  This
03283   ** step is skipped if the output is going to some other destination.
03284   */
03285   if( rc==SQLITE_OK && eDest==SRT_Callback ){
03286     generateColumnNames(pParse, pTabList, pEList);
03287   }
03288 
03289   sqliteFree(sAggInfo.aCol);
03290   sqliteFree(sAggInfo.aFunc);
03291   return rc;
03292 }