/*

** 2001 September 15

**

** The author disclaims copyright to this source code. In place of

** a legal notice, here is a blessing:

**

** May you do good and not evil.

** May you find forgiveness for yourself and forgive others.

** May you share freely, never taking more than you give.

**

*************************************************************************

** This file contains C code routines that are called by the parser

** to handle SELECT statements in SQLite.

*/

#include "sqliteInt.h"

/*

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

** the select structure itself.

*/

static void clearSelect(sqlite3 *db, Select *p){

sqlite3ExprListDelete(db, p->pEList);

sqlite3SrcListDelete(db, p->pSrc);

sqlite3ExprDelete(db, p->pWhere);

sqlite3ExprListDelete(db, p->pGroupBy);

sqlite3ExprDelete(db, p->pHaving);

sqlite3ExprListDelete(db, p->pOrderBy);

sqlite3SelectDelete(db, p->pPrior);

sqlite3ExprDelete(db, p->pLimit);

sqlite3ExprDelete(db, p->pOffset);

}

/*

** Initialize a SelectDest structure.

*/

void sqlite3SelectDestInit(SelectDest *pDest, int eDest, int iParm){

pDest->eDest = (u8)eDest;

pDest->iSDParm = iParm;

pDest->affSdst = 0;

pDest->iSdst = 0;

pDest->nSdst = 0;

}

/*

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

** structure.

*/

Select *sqlite3SelectNew(

Parse *pParse, /* Parsing context */

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

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

Expr *pWhere, /* the WHERE clause */

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

Expr *pHaving, /* the HAVING clause */

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

u16 selFlags, /* Flag parameters, such as SF_Distinct */

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

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

){

Select *pNew;

Select standin;

sqlite3 *db = pParse->db;

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

assert( db->mallocFailed || !pOffset || pLimit ); /* OFFSET implies LIMIT */

if( pNew==0 ){

assert( db->mallocFailed );

pNew = &standin;

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

}

if( pEList==0 ){

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

}

pNew->pEList = pEList;

if( pSrc==0 ) pSrc = sqlite3DbMallocZero(db, sizeof(*pSrc));

pNew->pSrc = pSrc;

pNew->pWhere = pWhere;

pNew->pGroupBy = pGroupBy;

pNew->pHaving = pHaving;

pNew->pOrderBy = pOrderBy;

pNew->selFlags = selFlags;

pNew->op = TK_SELECT;

pNew->pLimit = pLimit;

pNew->pOffset = pOffset;

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

pNew->addrOpenEphm[0] = -1;

pNew->addrOpenEphm[1] = -1;

pNew->addrOpenEphm[2] = -1;

if( db->mallocFailed ) {

clearSelect(db, pNew);

if( pNew!=&standin ) sqlite3DbFree(db, pNew);

pNew = 0;

}else{

assert( pNew->pSrc!=0 || pParse->nErr>0 );

}

assert( pNew!=&standin );

return pNew;

}

/*

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

*/

void sqlite3SelectDelete(sqlite3 *db, Select *p){

if( p ){

clearSelect(db, p);

sqlite3DbFree(db, p);

}

}

/*

** Given 1 to 3 identifiers preceding the JOIN keyword, determine the

** type of join. Return an integer constant that expresses that type

** in terms of the following bit values:

**

** JT_INNER

** JT_CROSS

** JT_OUTER

** JT_NATURAL

** JT_LEFT

** JT_RIGHT

**

** A full outer join is the combination of JT_LEFT and JT_RIGHT.

**

** If an illegal or unsupported join type is seen, then still return

** a join type, but put an error in the pParse structure.

*/

int sqlite3JoinType(Parse *pParse, Token *pA, Token *pB, Token *pC){

int jointype = 0;

Token *apAll[3];

Token *p;

/* 0123456789 123456789 123456789 123 */

static const char zKeyText[] = "naturaleftouterightfullinnercross";

static const struct {

u8 i; /* Beginning of keyword text in zKeyText[] */

u8 nChar; /* Length of the keyword in characters */

u8 code; /* Join type mask */

} aKeyword[] = {

/* natural */ { 0, 7, JT_NATURAL },

/* left */ { 6, 4, JT_LEFT|JT_OUTER },

/* outer */ { 10, 5, JT_OUTER },

/* right */ { 14, 5, JT_RIGHT|JT_OUTER },

/* full */ { 19, 4, JT_LEFT|JT_RIGHT|JT_OUTER },

/* inner */ { 23, 5, JT_INNER },

/* cross */ { 28, 5, JT_INNER|JT_CROSS },

};

int i, j;

apAll[0] = pA;

apAll[1] = pB;

apAll[2] = pC;

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

p = apAll[i];

for(j=0; j<ArraySize(aKeyword); j++){

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

&& sqlite3StrNICmp((char*)p->z, &zKeyText[aKeyword[j].i], p->n)==0 ){

jointype |= aKeyword[j].code;

break;

}

}

testcase( j==0 || j==1 || j==2 || j==3 || j==4 || j==5 || j==6 );

if( j>=ArraySize(aKeyword) ){

jointype |= JT_ERROR;

break;

}

}

if(

(jointype & (JT_INNER|JT_OUTER))==(JT_INNER|JT_OUTER) ||

(jointype & JT_ERROR)!=0

){

const char *zSp = " ";

assert( pB!=0 );

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

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

"%T %T%s%T", pA, pB, zSp, pC);

jointype = JT_INNER;

}else if( (jointype & JT_OUTER)!=0

&& (jointype & (JT_LEFT|JT_RIGHT))!=JT_LEFT ){

sqlite3ErrorMsg(pParse,

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

jointype = JT_INNER;

}

return jointype;

}

/*

** Return the index of a column in a table. Return -1 if the column

** is not contained in the table.

*/

static int columnIndex(Table *pTab, const char *zCol){

int i;

for(i=0; i<pTab->nCol; i++){

if( sqlite3StrICmp(pTab->aCol[i].zName, zCol)==0 ) return i;

}

return -1;

}

/*

** Search the first N tables in pSrc, from left to right, looking for a

** table that has a column named zCol.

**

** When found, set *piTab and *piCol to the table index and column index

** of the matching column and return TRUE.

**

** If not found, return FALSE.

*/

static int tableAndColumnIndex(

SrcList *pSrc, /* Array of tables to search */

int N, /* Number of tables in pSrc->a[] to search */

const char *zCol, /* Name of the column we are looking for */

int *piTab, /* Write index of pSrc->a[] here */

int *piCol /* Write index of pSrc->a[*piTab].pTab->aCol[] here */

){

int i; /* For looping over tables in pSrc */

int iCol; /* Index of column matching zCol */

assert( (piTab==0)==(piCol==0) ); /* Both or neither are NULL */

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

iCol = columnIndex(pSrc->a[i].pTab, zCol);

if( iCol>=0 ){

if( piTab ){

*piTab = i;

*piCol = iCol;

}

return 1;

}

}

return 0;

}

/*

** This function is used to add terms implied by JOIN syntax to the

** WHERE clause expression of a SELECT statement. The new term, which

** is ANDed with the existing WHERE clause, is of the form:

**

** (tab1.col1 = tab2.col2)

**

** where tab1 is the iSrc'th table in SrcList pSrc and tab2 is the

** (iSrc+1)'th. Column col1 is column iColLeft of tab1, and col2 is

** column iColRight of tab2.

*/

static void addWhereTerm(

Parse *pParse, /* Parsing context */

SrcList *pSrc, /* List of tables in FROM clause */

int iLeft, /* Index of first table to join in pSrc */

int iColLeft, /* Index of column in first table */

int iRight, /* Index of second table in pSrc */

int iColRight, /* Index of column in second table */

int isOuterJoin, /* True if this is an OUTER join */

Expr **ppWhere /* IN/OUT: The WHERE clause to add to */

){

sqlite3 *db = pParse->db;

Expr *pE1;

Expr *pE2;

Expr *pEq;

assert( iLeft<iRight );

assert( pSrc->nSrc>iRight );

assert( pSrc->a[iLeft].pTab );

assert( pSrc->a[iRight].pTab );

pE1 = sqlite3CreateColumnExpr(db, pSrc, iLeft, iColLeft);

pE2 = sqlite3CreateColumnExpr(db, pSrc, iRight, iColRight);

pEq = sqlite3PExpr(pParse, TK_EQ, pE1, pE2, 0);

if( pEq && isOuterJoin ){

ExprSetProperty(pEq, EP_FromJoin);

assert( !ExprHasAnyProperty(pEq, EP_TokenOnly|EP_Reduced) );

ExprSetIrreducible(pEq);

pEq->iRightJoinTable = (i16)pE2->iTable;

}

*ppWhere = sqlite3ExprAnd(db, *ppWhere, pEq);

}

/*

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

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

** expression.

**

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

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

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

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

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

** originated in the ON or USING clause.

**

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

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

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

** for cases like this:

**

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

**

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

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

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

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

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

** the output, which is incorrect.

*/

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

while( p ){

ExprSetProperty(p, EP_FromJoin);

assert( !ExprHasAnyProperty(p, EP_TokenOnly|EP_Reduced) );

ExprSetIrreducible(p);

p->iRightJoinTable = (i16)iTable;

setJoinExpr(p->pLeft, iTable);

p = p->pRight;

}

}

/*

** This routine processes the join information for a SELECT statement.

** ON and USING clauses are converted into extra terms of the WHERE clause.

** NATURAL joins also create extra WHERE clause terms.

**

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

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

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

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

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

** also attached to the left entry.

**

** This routine returns the number of errors encountered.

*/

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

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

int i, j; /* Loop counters */

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

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

pSrc = p->pSrc;

pLeft = &pSrc->a[0];

pRight = &pLeft[1];

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

Table *pLeftTab = pLeft->pTab;

Table *pRightTab = pRight->pTab;

int isOuter;

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

isOuter = (pRight->jointype & JT_OUTER)!=0;

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

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

*/

if( pRight->jointype & JT_NATURAL ){

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

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

"an ON or USING clause", 0);

return 1;

}

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

char *zName; /* Name of column in the right table */

int iLeft; /* Matching left table */

int iLeftCol; /* Matching column in the left table */

zName = pRightTab->aCol[j].zName;

if( tableAndColumnIndex(pSrc, i+1, zName, &iLeft, &iLeftCol) ){

addWhereTerm(pParse, pSrc, iLeft, iLeftCol, i+1, j,

isOuter, &p->pWhere);

}

}

}

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

*/

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

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

"clauses in the same join");

return 1;

}

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

** an AND operator.

*/

if( pRight->pOn ){

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

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

pRight->pOn = 0;

}

/* Create extra terms on the WHERE clause for each column named

** in the USING clause. Example: If the two tables to be joined are

** A and B and the USING clause names X, Y, and Z, then add this

** to the WHERE clause: A.X=B.X AND A.Y=B.Y AND A.Z=B.Z

** Report an error if any column mentioned in the USING clause is

** not contained in both tables to be joined.

*/

if( pRight->pUsing ){

IdList *pList = pRight->pUsing;

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

char *zName; /* Name of the term in the USING clause */

int iLeft; /* Table on the left with matching column name */

int iLeftCol; /* Column number of matching column on the left */

int iRightCol; /* Column number of matching column on the right */

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

iRightCol = columnIndex(pRightTab, zName);

if( iRightCol<0

|| !tableAndColumnIndex(pSrc, i+1, zName, &iLeft, &iLeftCol)

){

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

"not present in both tables", zName);

return 1;

}

addWhereTerm(pParse, pSrc, iLeft, iLeftCol, i+1, iRightCol,

isOuter, &p->pWhere);

}

}

}

return 0;

}

/*

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

** stack into the sorter.

*/

static void pushOntoSorter(

Parse *pParse, /* Parser context */

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

Select *pSelect, /* The whole SELECT statement */

int regData /* Register holding data to be sorted */

){

Vdbe *v = pParse->pVdbe;

int nExpr = pOrderBy->nExpr;

int regBase = sqlite3GetTempRange(pParse, nExpr+2);

int regRecord = sqlite3GetTempReg(pParse);

int op;

sqlite3ExprCacheClear(pParse);

sqlite3ExprCodeExprList(pParse, pOrderBy, regBase, 0);

sqlite3VdbeAddOp2(v, OP_Sequence, pOrderBy->iECursor, regBase+nExpr);

sqlite3ExprCodeMove(pParse, regData, regBase+nExpr+1, 1);

sqlite3VdbeAddOp3(v, OP_MakeRecord, regBase, nExpr + 2, regRecord);

if( pSelect->selFlags & SF_UseSorter ){

op = OP_SorterInsert;

}else{

op = OP_IdxInsert;

}

sqlite3VdbeAddOp2(v, op, pOrderBy->iECursor, regRecord);

sqlite3ReleaseTempReg(pParse, regRecord);

sqlite3ReleaseTempRange(pParse, regBase, nExpr+2);

if( pSelect->iLimit ){

int addr1, addr2;

int iLimit;

if( pSelect->iOffset ){

iLimit = pSelect->iOffset+1;

}else{

iLimit = pSelect->iLimit;

}

addr1 = sqlite3VdbeAddOp1(v, OP_IfZero, iLimit);

sqlite3VdbeAddOp2(v, OP_AddImm, iLimit, -1);

addr2 = sqlite3VdbeAddOp0(v, OP_Goto);

sqlite3VdbeJumpHere(v, addr1);

sqlite3VdbeAddOp1(v, OP_Last, pOrderBy->iECursor);

sqlite3VdbeAddOp1(v, OP_Delete, pOrderBy->iECursor);

sqlite3VdbeJumpHere(v, addr2);

}

}

/*

** Add code to implement the OFFSET

*/

static void codeOffset(

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

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

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

){

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

int addr;

sqlite3VdbeAddOp2(v, OP_AddImm, p->iOffset, -1);

addr = sqlite3VdbeAddOp1(v, OP_IfNeg, p->iOffset);

sqlite3VdbeAddOp2(v, OP_Goto, 0, iContinue);

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

sqlite3VdbeJumpHere(v, addr);

}

}

/*

** Add code that will check to make sure the N registers starting at iMem

** form a distinct entry. iTab is a sorting index that holds previously

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

** if the current N values are new.

**

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

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

*/

static void codeDistinct(

Parse *pParse, /* Parsing and code generating context */

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

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

int N, /* Number of elements */

int iMem /* First element */

){

Vdbe *v;

int r1;

v = pParse->pVdbe;

r1 = sqlite3GetTempReg(pParse);

sqlite3VdbeAddOp4Int(v, OP_Found, iTab, addrRepeat, iMem, N);

sqlite3VdbeAddOp3(v, OP_MakeRecord, iMem, N, r1);

sqlite3VdbeAddOp2(v, OP_IdxInsert, iTab, r1);

sqlite3ReleaseTempReg(pParse, r1);

}

#ifndef SQLITE_OMIT_SUBQUERY

/*

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

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

** column. We do this in a subroutine because the error used to occur

** in multiple places. (The error only occurs in one place now, but we

** retain the subroutine to minimize code disruption.)

*/

static int checkForMultiColumnSelectError(

Parse *pParse, /* Parse context. */

SelectDest *pDest, /* Destination of SELECT results */

int nExpr /* Number of result columns returned by SELECT */

){

int eDest = pDest->eDest;

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

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

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

return 1;

}else{

return 0;

}

}

#endif

/*

** An instance of the following object is used to record information about

** how to process the DISTINCT keyword, to simplify passing that information

** into the selectInnerLoop() routine.

*/

typedef struct DistinctCtx DistinctCtx;

struct DistinctCtx {

u8 isTnct; /* True if the DISTINCT keyword is present */

u8 eTnctType; /* One of the WHERE_DISTINCT_* operators */

int tabTnct; /* Ephemeral table used for DISTINCT processing */

int addrTnct; /* Address of OP_OpenEphemeral opcode for tabTnct */

};

/*

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

** of a SELECT.

**

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

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

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

** datatypes for each column.

*/

static void selectInnerLoop(

Parse *pParse, /* The parser context */

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

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

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

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

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

DistinctCtx *pDistinct, /* If not NULL, info on how to process DISTINCT */

SelectDest *pDest, /* How to dispose of the results */

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

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

){

Vdbe *v = pParse->pVdbe;

int i;

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

int regResult; /* Start of memory holding result set */

int eDest = pDest->eDest; /* How to dispose of results */

int iParm = pDest->iSDParm; /* First argument to disposal method */

int nResultCol; /* Number of result columns */

assert( v );

if( NEVER(v==0) ) return;

assert( pEList!=0 );

hasDistinct = pDistinct ? pDistinct->eTnctType : WHERE_DISTINCT_NOOP;

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

codeOffset(v, p, iContinue);

}

/* Pull the requested columns.

*/

if( nColumn>0 ){

nResultCol = nColumn;

}else{

nResultCol = pEList->nExpr;

}

if( pDest->iSdst==0 ){

pDest->iSdst = pParse->nMem+1;

pDest->nSdst = nResultCol;

pParse->nMem += nResultCol;

}else{

assert( pDest->nSdst==nResultCol );

}

regResult = pDest->iSdst;

if( nColumn>0 ){

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

sqlite3VdbeAddOp3(v, OP_Column, srcTab, i, regResult+i);

}

}else if( eDest!=SRT_Exists ){

/* If the destination is an EXISTS(...) expression, the actual

** values returned by the SELECT are not required.

*/

sqlite3ExprCacheClear(pParse);

sqlite3ExprCodeExprList(pParse, pEList, regResult, eDest==SRT_Output);

}

nColumn = nResultCol;

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

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

** part of the result.

*/

if( hasDistinct ){

assert( pEList!=0 );

assert( pEList->nExpr==nColumn );

switch( pDistinct->eTnctType ){

case WHERE_DISTINCT_ORDERED: {

VdbeOp *pOp; /* No longer required OpenEphemeral instr. */

int iJump; /* Jump destination */

int regPrev; /* Previous row content */

/* Allocate space for the previous row */

regPrev = pParse->nMem+1;

pParse->nMem += nColumn;

/* Change the OP_OpenEphemeral coded earlier to an OP_Null

** sets the MEM_Cleared bit on the first register of the

** previous value. This will cause the OP_Ne below to always

** fail on the first iteration of the loop even if the first

** row is all NULLs.

*/

sqlite3VdbeChangeToNoop(v, pDistinct->addrTnct);

pOp = sqlite3VdbeGetOp(v, pDistinct->addrTnct);

pOp->opcode = OP_Null;

pOp->p1 = 1;

pOp->p2 = regPrev;

iJump = sqlite3VdbeCurrentAddr(v) + nColumn;

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

CollSeq *pColl = sqlite3ExprCollSeq(pParse, pEList->a[i].pExpr);

if( i<nColumn-1 ){

sqlite3VdbeAddOp3(v, OP_Ne, regResult+i, iJump, regPrev+i);

}else{

sqlite3VdbeAddOp3(v, OP_Eq, regResult+i, iContinue, regPrev+i);

}

sqlite3VdbeChangeP4(v, -1, (const char *)pColl, P4_COLLSEQ);

sqlite3VdbeChangeP5(v, SQLITE_NULLEQ);

}

assert( sqlite3VdbeCurrentAddr(v)==iJump );

sqlite3VdbeAddOp3(v, OP_Copy, regResult, regPrev, nColumn-1);

break;

}

case WHERE_DISTINCT_UNIQUE: {

sqlite3VdbeChangeToNoop(v, pDistinct->addrTnct);

break;

}

default: {

assert( pDistinct->eTnctType==WHERE_DISTINCT_UNORDERED );

codeDistinct(pParse, pDistinct->tabTnct, iContinue, nColumn, regResult);

break;

}

}

if( pOrderBy==0 ){

codeOffset(v, p, iContinue);

}

}

switch( eDest ){

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

** table iParm.

*/

#ifndef SQLITE_OMIT_COMPOUND_SELECT

case SRT_Union: {

int r1;

r1 = sqlite3GetTempReg(pParse);

sqlite3VdbeAddOp3(v, OP_MakeRecord, regResult, nColumn, r1);

sqlite3VdbeAddOp2(v, OP_IdxInsert, iParm, r1);

sqlite3ReleaseTempReg(pParse, r1);

break;

}

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

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

** the temporary table iParm.

*/

case SRT_Except: {

sqlite3VdbeAddOp3(v, OP_IdxDelete, iParm, regResult, nColumn);

break;

}

#endif

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

*/

case SRT_Table:

case SRT_EphemTab: {

int r1 = sqlite3GetTempReg(pParse);

testcase( eDest==SRT_Table );

testcase( eDest==SRT_EphemTab );

sqlite3VdbeAddOp3(v, OP_MakeRecord, regResult, nColumn, r1);

if( pOrderBy ){

pushOntoSorter(pParse, pOrderBy, p, r1);

}else{

int r2 = sqlite3GetTempReg(pParse);

sqlite3VdbeAddOp2(v, OP_NewRowid, iParm, r2);

sqlite3VdbeAddOp3(v, OP_Insert, iParm, r1, r2);

sqlite3VdbeChangeP5(v, OPFLAG_APPEND);

sqlite3ReleaseTempReg(pParse, r2);

}

sqlite3ReleaseTempReg(pParse, r1);

break;

}

#ifndef SQLITE_OMIT_SUBQUERY

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

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

** item into the set table with bogus data.

*/

case SRT_Set: {

assert( nColumn==1 );

pDest->affSdst =

sqlite3CompareAffinity(pEList->a[0].pExpr, pDest->affSdst);

if( pOrderBy ){

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

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

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

** case the order does matter */

pushOntoSorter(pParse, pOrderBy, p, regResult);

}else{

int r1 = sqlite3GetTempReg(pParse);

sqlite3VdbeAddOp4(v, OP_MakeRecord, regResult,1,r1, &pDest->affSdst, 1);

sqlite3ExprCacheAffinityChange(pParse, regResult, 1);

sqlite3VdbeAddOp2(v, OP_IdxInsert, iParm, r1);

sqlite3ReleaseTempReg(pParse, r1);

}

break;

}

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

*/

case SRT_Exists: {

sqlite3VdbeAddOp2(v, OP_Integer, 1, iParm);

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

break;

}

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

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

** of the scan loop.

*/

case SRT_Mem: {

assert( nColumn==1 );

if( pOrderBy ){

pushOntoSorter(pParse, pOrderBy, p, regResult);

}else{

sqlite3ExprCodeMove(pParse, regResult, iParm, 1);

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

}

break;

}

#endif /* #ifndef SQLITE_OMIT_SUBQUERY */

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

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

** popping the data from the stack.

*/

case SRT_Coroutine:

case SRT_Output: {

testcase( eDest==SRT_Coroutine );

testcase( eDest==SRT_Output );

if( pOrderBy ){

int r1 = sqlite3GetTempReg(pParse);

sqlite3VdbeAddOp3(v, OP_MakeRecord, regResult, nColumn, r1);

pushOntoSorter(pParse, pOrderBy, p, r1);

sqlite3ReleaseTempReg(pParse, r1);

}else if( eDest==SRT_Coroutine ){

sqlite3VdbeAddOp1(v, OP_Yield, pDest->iSDParm);

}else{

sqlite3VdbeAddOp2(v, OP_ResultRow, regResult, nColumn);

sqlite3ExprCacheAffinityChange(pParse, regResult, nColumn);

}

break;

}

#if !defined(SQLITE_OMIT_TRIGGER)

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

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

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

** about the actual results of the select.

*/

default: {

assert( eDest==SRT_Discard );

break;

}

#endif

}

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

** there is a sorter, in which case the sorter has already limited

** the output for us.

*/

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

sqlite3VdbeAddOp3(v, OP_IfZero, p->iLimit, iBreak, -1);

}

}

/*

** Allocate a KeyInfo object sufficient for an index of N columns.

**

** Actually, always allocate one extra column for the rowid at the end

** of the index. So the KeyInfo returned will have space sufficient for

** N+1 columns.

*/

KeyInfo *sqlite3KeyInfoAlloc(sqlite3 *db, int N){

KeyInfo *p = sqlite3DbMallocZero(db,

sizeof(KeyInfo) + (N+1)*(sizeof(CollSeq*)+1));

if( p ){

p->aSortOrder = (u8*)&p->aColl[N+1];

p->nField = (u16)N;

p->enc = ENC(db);

p->db = db;

}

return p;

}

/*

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

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

**

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

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

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

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

** index to implement a DISTINCT test.

**

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

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

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

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

*/

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

int nExpr;

KeyInfo *pInfo;

struct ExprList_item *pItem;

sqlite3 *db = pParse->db;

int i;

nExpr = pList->nExpr;

pInfo = sqlite3KeyInfoAlloc(db, nExpr);

if( pInfo ){

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

CollSeq *pColl;

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

if( !pColl ) pColl = db->pDfltColl;

pInfo->aColl[i] = pColl;

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

}

}

return pInfo;

}

#ifndef SQLITE_OMIT_COMPOUND_SELECT

/*

** Name of the connection operator, used for error messages.

*/

static const char *selectOpName(int id){

char *z;

switch( id ){

case TK_ALL: z = "UNION ALL"; break;

case TK_INTERSECT: z = "INTERSECT"; break;

case TK_EXCEPT: z = "EXCEPT"; break;

default: z = "UNION"; break;

}

return z;

}

#endif /* SQLITE_OMIT_COMPOUND_SELECT */

#ifndef SQLITE_OMIT_EXPLAIN

/*

** Unless an "EXPLAIN QUERY PLAN" command is being processed, this function

** is a no-op. Otherwise, it adds a single row of output to the EQP result,

** where the caption is of the form:

**

** "USE TEMP B-TREE FOR xxx"

**

** where xxx is one of "DISTINCT", "ORDER BY" or "GROUP BY". Exactly which

** is determined by the zUsage argument.

*/

static void explainTempTable(Parse *pParse, const char *zUsage){

if( pParse->explain==2 ){

Vdbe *v = pParse->pVdbe;

char *zMsg = sqlite3MPrintf(pParse->db, "USE TEMP B-TREE FOR %s", zUsage);

sqlite3VdbeAddOp4(v, OP_Explain, pParse->iSelectId, 0, 0, zMsg, P4_DYNAMIC);

}

}

/*

** Assign expression b to lvalue a. A second, no-op, version of this macro

** is provided when SQLITE_OMIT_EXPLAIN is defined. This allows the code

** in sqlite3Select() to assign values to structure member variables that

** only exist if SQLITE_OMIT_EXPLAIN is not defined without polluting the

** code with #ifndef directives.

*/

# define explainSetInteger(a, b) a = b

#else

/* No-op versions of the explainXXX() functions and macros. */

# define explainTempTable(y,z)

# define explainSetInteger(y,z)

#endif

#if !defined(SQLITE_OMIT_EXPLAIN) && !defined(SQLITE_OMIT_COMPOUND_SELECT)

/*

** Unless an "EXPLAIN QUERY PLAN" command is being processed, this function

** is a no-op. Otherwise, it adds a single row of output to the EQP result,

** where the caption is of one of the two forms:

**

** "COMPOSITE SUBQUERIES iSub1 and iSub2 (op)"

** "COMPOSITE SUBQUERIES iSub1 and iSub2 USING TEMP B-TREE (op)"

**

** where iSub1 and iSub2 are the integers passed as the corresponding

** function parameters, and op is the text representation of the parameter

** of the same name. The parameter "op" must be one of TK_UNION, TK_EXCEPT,

** TK_INTERSECT or TK_ALL. The first form is used if argument bUseTmp is

** false, or the second form if it is true.

*/

static void explainComposite(

Parse *pParse, /* Parse context */

int op, /* One of TK_UNION, TK_EXCEPT etc. */

int iSub1, /* Subquery id 1 */

int iSub2, /* Subquery id 2 */

int bUseTmp /* True if a temp table was used */

){

assert( op==TK_UNION || op==TK_EXCEPT || op==TK_INTERSECT || op==TK_ALL );

if( pParse->explain==2 ){

Vdbe *v = pParse->pVdbe;

char *zMsg = sqlite3MPrintf(

pParse->db, "COMPOUND SUBQUERIES %d AND %d %s(%s)", iSub1, iSub2,

bUseTmp?"USING TEMP B-TREE ":"", selectOpName(op)

);

sqlite3VdbeAddOp4(v, OP_Explain, pParse->iSelectId, 0, 0, zMsg, P4_DYNAMIC);

}

}

#else

/* No-op versions of the explainXXX() functions and macros. */

# define explainComposite(v,w,x,y,z)

#endif

/*

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

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

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

** routine generates the code needed to do that.

*/

static void generateSortTail(

Parse *pParse, /* Parsing context */

Select *p, /* The SELECT statement */

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

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

SelectDest *pDest /* Write the sorted results here */

){

int addrBreak = sqlite3VdbeMakeLabel(v); /* Jump here to exit loop */

int addrContinue = sqlite3VdbeMakeLabel(v); /* Jump here for next cycle */

int addr;

int iTab;

int pseudoTab = 0;

ExprList *pOrderBy = p->pOrderBy;

int eDest = pDest->eDest;

int iParm = pDest->iSDParm;

int regRow;

int regRowid;

iTab = pOrderBy->iECursor;

regRow = sqlite3GetTempReg(pParse);

if( eDest==SRT_Output || eDest==SRT_Coroutine ){

pseudoTab = pParse->nTab++;

sqlite3VdbeAddOp3(v, OP_OpenPseudo, pseudoTab, regRow, nColumn);

regRowid = 0;

}else{

regRowid = sqlite3GetTempReg(pParse);

}

if( p->selFlags & SF_UseSorter ){

int regSortOut = ++pParse->nMem;

int ptab2 = pParse->nTab++;

sqlite3VdbeAddOp3(v, OP_OpenPseudo, ptab2, regSortOut, pOrderBy->nExpr+2);

addr = 1 + sqlite3VdbeAddOp2(v, OP_SorterSort, iTab, addrBreak);

codeOffset(v, p, addrContinue);

sqlite3VdbeAddOp2(v, OP_SorterData, iTab, regSortOut);

sqlite3VdbeAddOp3(v, OP_Column, ptab2, pOrderBy->nExpr+1, regRow);

sqlite3VdbeChangeP5(v, OPFLAG_CLEARCACHE);

}else{

addr = 1 + sqlite3VdbeAddOp2(v, OP_Sort, iTab, addrBreak);

codeOffset(v, p, addrContinue);

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

}

switch( eDest ){

case SRT_Table:

case SRT_EphemTab: {

testcase( eDest==SRT_Table );

testcase( eDest==SRT_EphemTab );