Symaptic: os/persistentdata/persistentstorage/sql/SQLite/select.c@260cb5ec6c19 (annotated)

sl@0	1	/*
sl@0	2	** 2001 September 15
sl@0	3	**
sl@0	4	** The author disclaims copyright to this source code. In place of
sl@0	5	** a legal notice, here is a blessing:
sl@0	6	**
sl@0	7	** May you do good and not evil.
sl@0	8	** May you find forgiveness for yourself and forgive others.
sl@0	9	** May you share freely, never taking more than you give.
sl@0	10	**
sl@0	11	*************************************************************************
sl@0	12	** This file contains C code routines that are called by the parser
sl@0	13	** to handle SELECT statements in SQLite.
sl@0	14	**
sl@0	15	** $Id: select.c,v 1.463 2008/08/04 03:51:24 danielk1977 Exp $
sl@0	16	*/
sl@0	17	#include "sqliteInt.h"
sl@0	18
sl@0	19
sl@0	20	/*
sl@0	21	** Delete all the content of a Select structure but do not deallocate
sl@0	22	** the select structure itself.
sl@0	23	*/
sl@0	24	static void clearSelect(sqlite3 db, Select p){
sl@0	25	sqlite3ExprListDelete(db, p->pEList);
sl@0	26	sqlite3SrcListDelete(db, p->pSrc);
sl@0	27	sqlite3ExprDelete(db, p->pWhere);
sl@0	28	sqlite3ExprListDelete(db, p->pGroupBy);
sl@0	29	sqlite3ExprDelete(db, p->pHaving);
sl@0	30	sqlite3ExprListDelete(db, p->pOrderBy);
sl@0	31	sqlite3SelectDelete(db, p->pPrior);
sl@0	32	sqlite3ExprDelete(db, p->pLimit);
sl@0	33	sqlite3ExprDelete(db, p->pOffset);
sl@0	34	}
sl@0	35
sl@0	36	/*
sl@0	37	** Initialize a SelectDest structure.
sl@0	38	*/
sl@0	39	void sqlite3SelectDestInit(SelectDest *pDest, int eDest, int iParm){
sl@0	40	pDest->eDest = eDest;
sl@0	41	pDest->iParm = iParm;
sl@0	42	pDest->affinity = 0;
sl@0	43	pDest->iMem = 0;
sl@0	44	pDest->nMem = 0;
sl@0	45	}
sl@0	46
sl@0	47
sl@0	48	/*
sl@0	49	** Allocate a new Select structure and return a pointer to that
sl@0	50	** structure.
sl@0	51	*/
sl@0	52	Select *sqlite3SelectNew(
sl@0	53	Parse pParse, / Parsing context */
sl@0	54	ExprList pEList, / which columns to include in the result */
sl@0	55	SrcList pSrc, / the FROM clause -- which tables to scan */
sl@0	56	Expr pWhere, / the WHERE clause */
sl@0	57	ExprList pGroupBy, / the GROUP BY clause */
sl@0	58	Expr pHaving, / the HAVING clause */
sl@0	59	ExprList pOrderBy, / the ORDER BY clause */
sl@0	60	int isDistinct, /* true if the DISTINCT keyword is present */
sl@0	61	Expr pLimit, / LIMIT value. NULL means not used */
sl@0	62	Expr pOffset / OFFSET value. NULL means no offset */
sl@0	63	){
sl@0	64	Select *pNew;
sl@0	65	Select standin;
sl@0	66	sqlite3 *db = pParse->db;
sl@0	67	pNew = sqlite3DbMallocZero(db, sizeof(*pNew) );
sl@0	68	assert( !pOffset \|\| pLimit ); /* Can't have OFFSET without LIMIT. */
sl@0	69	if( pNew==0 ){
sl@0	70	pNew = &standin;
sl@0	71	memset(pNew, 0, sizeof(*pNew));
sl@0	72	}
sl@0	73	if( pEList==0 ){
sl@0	74	pEList = sqlite3ExprListAppend(pParse, 0, sqlite3Expr(db,TK_ALL,0,0,0), 0);
sl@0	75	}
sl@0	76	pNew->pEList = pEList;
sl@0	77	pNew->pSrc = pSrc;
sl@0	78	pNew->pWhere = pWhere;
sl@0	79	pNew->pGroupBy = pGroupBy;
sl@0	80	pNew->pHaving = pHaving;
sl@0	81	pNew->pOrderBy = pOrderBy;
sl@0	82	pNew->isDistinct = isDistinct;
sl@0	83	pNew->op = TK_SELECT;
sl@0	84	assert( pOffset==0 \|\| pLimit!=0 );
sl@0	85	pNew->pLimit = pLimit;
sl@0	86	pNew->pOffset = pOffset;
sl@0	87	pNew->addrOpenEphm[0] = -1;
sl@0	88	pNew->addrOpenEphm[1] = -1;
sl@0	89	pNew->addrOpenEphm[2] = -1;
sl@0	90	if( pNew==&standin) {
sl@0	91	clearSelect(db, pNew);
sl@0	92	pNew = 0;
sl@0	93	}
sl@0	94	return pNew;
sl@0	95	}
sl@0	96
sl@0	97	/*
sl@0	98	** Delete the given Select structure and all of its substructures.
sl@0	99	*/
sl@0	100	void sqlite3SelectDelete(sqlite3 db, Select p){
sl@0	101	if( p ){
sl@0	102	clearSelect(db, p);
sl@0	103	sqlite3DbFree(db, p);
sl@0	104	}
sl@0	105	}
sl@0	106
sl@0	107	/*
sl@0	108	** Given 1 to 3 identifiers preceeding the JOIN keyword, determine the
sl@0	109	** type of join. Return an integer constant that expresses that type
sl@0	110	** in terms of the following bit values:
sl@0	111	**
sl@0	112	** JT_INNER
sl@0	113	** JT_CROSS
sl@0	114	** JT_OUTER
sl@0	115	** JT_NATURAL
sl@0	116	** JT_LEFT
sl@0	117	** JT_RIGHT
sl@0	118	**
sl@0	119	** A full outer join is the combination of JT_LEFT and JT_RIGHT.
sl@0	120	**
sl@0	121	** If an illegal or unsupported join type is seen, then still return
sl@0	122	** a join type, but put an error in the pParse structure.
sl@0	123	*/
sl@0	124	int sqlite3JoinType(Parse pParse, Token pA, Token pB, Token pC){
sl@0	125	int jointype = 0;
sl@0	126	Token *apAll[3];
sl@0	127	Token *p;
sl@0	128	static const struct {
sl@0	129	const char zKeyword[8];
sl@0	130	u8 nChar;
sl@0	131	u8 code;
sl@0	132	} keywords[] = {
sl@0	133	{ "natural", 7, JT_NATURAL },
sl@0	134	{ "left", 4, JT_LEFT\|JT_OUTER },
sl@0	135	{ "right", 5, JT_RIGHT\|JT_OUTER },
sl@0	136	{ "full", 4, JT_LEFT\|JT_RIGHT\|JT_OUTER },
sl@0	137	{ "outer", 5, JT_OUTER },
sl@0	138	{ "inner", 5, JT_INNER },
sl@0	139	{ "cross", 5, JT_INNER\|JT_CROSS },
sl@0	140	};
sl@0	141	int i, j;
sl@0	142	apAll[0] = pA;
sl@0	143	apAll[1] = pB;
sl@0	144	apAll[2] = pC;
sl@0	145	for(i=0; i<3 && apAll[i]; i++){
sl@0	146	p = apAll[i];
sl@0	147	for(j=0; j<sizeof(keywords)/sizeof(keywords[0]); j++){
sl@0	148	if( p->n==keywords[j].nChar
sl@0	149	&& sqlite3StrNICmp((char*)p->z, keywords[j].zKeyword, p->n)==0 ){
sl@0	150	jointype \|= keywords[j].code;
sl@0	151	break;
sl@0	152	}
sl@0	153	}
sl@0	154	if( j>=sizeof(keywords)/sizeof(keywords[0]) ){
sl@0	155	jointype \|= JT_ERROR;
sl@0	156	break;
sl@0	157	}
sl@0	158	}
sl@0	159	if(
sl@0	160	(jointype & (JT_INNER\|JT_OUTER))==(JT_INNER\|JT_OUTER) \|\|
sl@0	161	(jointype & JT_ERROR)!=0
sl@0	162	){
sl@0	163	const char *zSp = " ";
sl@0	164	assert( pB!=0 );
sl@0	165	if( pC==0 ){ zSp++; }
sl@0	166	sqlite3ErrorMsg(pParse, "unknown or unsupported join type: "
sl@0	167	"%T %T%s%T", pA, pB, zSp, pC);
sl@0	168	jointype = JT_INNER;
sl@0	169	}else if( jointype & JT_RIGHT ){
sl@0	170	sqlite3ErrorMsg(pParse,
sl@0	171	"RIGHT and FULL OUTER JOINs are not currently supported");
sl@0	172	jointype = JT_INNER;
sl@0	173	}
sl@0	174	return jointype;
sl@0	175	}
sl@0	176
sl@0	177	/*
sl@0	178	** Return the index of a column in a table. Return -1 if the column
sl@0	179	** is not contained in the table.
sl@0	180	*/
sl@0	181	static int columnIndex(Table pTab, const char zCol){
sl@0	182	int i;
sl@0	183	for(i=0; i<pTab->nCol; i++){
sl@0	184	if( sqlite3StrICmp(pTab->aCol[i].zName, zCol)==0 ) return i;
sl@0	185	}
sl@0	186	return -1;
sl@0	187	}
sl@0	188
sl@0	189	/*
sl@0	190	** Set the value of a token to a '\000'-terminated string.
sl@0	191	*/
sl@0	192	static void setToken(Token p, const char z){
sl@0	193	p->z = (u8*)z;
sl@0	194	p->n = z ? strlen(z) : 0;
sl@0	195	p->dyn = 0;
sl@0	196	}
sl@0	197
sl@0	198	/*
sl@0	199	** Set the token to the double-quoted and escaped version of the string pointed
sl@0	200	** to by z. For example;
sl@0	201	**
sl@0	202	** {a"bc} -> {"a""bc"}
sl@0	203	*/
sl@0	204	static void setQuotedToken(Parse pParse, Token p, const char *z){
sl@0	205
sl@0	206	/* Check if the string contains any " characters. If it does, then
sl@0	207	** this function will malloc space to create a quoted version of
sl@0	208	** the string in. Otherwise, save a call to sqlite3MPrintf() by
sl@0	209	** just copying the pointer to the string.
sl@0	210	*/
sl@0	211	const char *z2 = z;
sl@0	212	while( *z2 ){
sl@0	213	if( *z2=='"' ) break;
sl@0	214	z2++;
sl@0	215	}
sl@0	216
sl@0	217	if( *z2 ){
sl@0	218	/* String contains " characters - copy and quote the string. */
sl@0	219	p->z = (u8 *)sqlite3MPrintf(pParse->db, "\"%w\"", z);
sl@0	220	if( p->z ){
sl@0	221	p->n = strlen((char *)p->z);
sl@0	222	p->dyn = 1;
sl@0	223	}
sl@0	224	}else{
sl@0	225	/* String contains no " characters - copy the pointer. */
sl@0	226	p->z = (u8*)z;
sl@0	227	p->n = (z2 - z);
sl@0	228	p->dyn = 0;
sl@0	229	}
sl@0	230	}
sl@0	231
sl@0	232	/*
sl@0	233	** Create an expression node for an identifier with the name of zName
sl@0	234	*/
sl@0	235	Expr sqlite3CreateIdExpr(Parse pParse, const char *zName){
sl@0	236	Token dummy;
sl@0	237	setToken(&dummy, zName);
sl@0	238	return sqlite3PExpr(pParse, TK_ID, 0, 0, &dummy);
sl@0	239	}
sl@0	240
sl@0	241	/*
sl@0	242	** Add a term to the WHERE expression in *ppExpr that requires the
sl@0	243	** zCol column to be equal in the two tables pTab1 and pTab2.
sl@0	244	*/
sl@0	245	static void addWhereTerm(
sl@0	246	Parse pParse, / Parsing context */
sl@0	247	const char zCol, / Name of the column */
sl@0	248	const Table pTab1, / First table */
sl@0	249	const char zAlias1, / Alias for first table. May be NULL */
sl@0	250	const Table pTab2, / Second table */
sl@0	251	const char zAlias2, / Alias for second table. May be NULL */
sl@0	252	int iRightJoinTable, /* VDBE cursor for the right table */
sl@0	253	Expr *ppExpr, / Add the equality term to this expression */
sl@0	254	int isOuterJoin /* True if dealing with an OUTER join */
sl@0	255	){
sl@0	256	Expr pE1a, pE1b, *pE1c;
sl@0	257	Expr pE2a, pE2b, *pE2c;
sl@0	258	Expr *pE;
sl@0	259
sl@0	260	pE1a = sqlite3CreateIdExpr(pParse, zCol);
sl@0	261	pE2a = sqlite3CreateIdExpr(pParse, zCol);
sl@0	262	if( zAlias1==0 ){
sl@0	263	zAlias1 = pTab1->zName;
sl@0	264	}
sl@0	265	pE1b = sqlite3CreateIdExpr(pParse, zAlias1);
sl@0	266	if( zAlias2==0 ){
sl@0	267	zAlias2 = pTab2->zName;
sl@0	268	}
sl@0	269	pE2b = sqlite3CreateIdExpr(pParse, zAlias2);
sl@0	270	pE1c = sqlite3PExpr(pParse, TK_DOT, pE1b, pE1a, 0);
sl@0	271	pE2c = sqlite3PExpr(pParse, TK_DOT, pE2b, pE2a, 0);
sl@0	272	pE = sqlite3PExpr(pParse, TK_EQ, pE1c, pE2c, 0);
sl@0	273	if( pE && isOuterJoin ){
sl@0	274	ExprSetProperty(pE, EP_FromJoin);
sl@0	275	pE->iRightJoinTable = iRightJoinTable;
sl@0	276	}
sl@0	277	ppExpr = sqlite3ExprAnd(pParse->db,ppExpr, pE);
sl@0	278	}
sl@0	279
sl@0	280	/*
sl@0	281	** Set the EP_FromJoin property on all terms of the given expression.
sl@0	282	** And set the Expr.iRightJoinTable to iTable for every term in the
sl@0	283	** expression.
sl@0	284	**
sl@0	285	** The EP_FromJoin property is used on terms of an expression to tell
sl@0	286	** the LEFT OUTER JOIN processing logic that this term is part of the
sl@0	287	** join restriction specified in the ON or USING clause and not a part
sl@0	288	** of the more general WHERE clause. These terms are moved over to the
sl@0	289	** WHERE clause during join processing but we need to remember that they
sl@0	290	** originated in the ON or USING clause.
sl@0	291	**
sl@0	292	** The Expr.iRightJoinTable tells the WHERE clause processing that the
sl@0	293	** expression depends on table iRightJoinTable even if that table is not
sl@0	294	** explicitly mentioned in the expression. That information is needed
sl@0	295	** for cases like this:
sl@0	296	**
sl@0	297	** SELECT * FROM t1 LEFT JOIN t2 ON t1.a=t2.b AND t1.x=5
sl@0	298	**
sl@0	299	** The where clause needs to defer the handling of the t1.x=5
sl@0	300	** term until after the t2 loop of the join. In that way, a
sl@0	301	** NULL t2 row will be inserted whenever t1.x!=5. If we do not
sl@0	302	** defer the handling of t1.x=5, it will be processed immediately
sl@0	303	** after the t1 loop and rows with t1.x!=5 will never appear in
sl@0	304	** the output, which is incorrect.
sl@0	305	*/
sl@0	306	static void setJoinExpr(Expr *p, int iTable){
sl@0	307	while( p ){
sl@0	308	ExprSetProperty(p, EP_FromJoin);
sl@0	309	p->iRightJoinTable = iTable;
sl@0	310	setJoinExpr(p->pLeft, iTable);
sl@0	311	p = p->pRight;
sl@0	312	}
sl@0	313	}
sl@0	314
sl@0	315	/*
sl@0	316	** This routine processes the join information for a SELECT statement.
sl@0	317	** ON and USING clauses are converted into extra terms of the WHERE clause.
sl@0	318	** NATURAL joins also create extra WHERE clause terms.
sl@0	319	**
sl@0	320	** The terms of a FROM clause are contained in the Select.pSrc structure.
sl@0	321	** The left most table is the first entry in Select.pSrc. The right-most
sl@0	322	** table is the last entry. The join operator is held in the entry to
sl@0	323	** the left. Thus entry 0 contains the join operator for the join between
sl@0	324	** entries 0 and 1. Any ON or USING clauses associated with the join are
sl@0	325	** also attached to the left entry.
sl@0	326	**
sl@0	327	** This routine returns the number of errors encountered.
sl@0	328	*/
sl@0	329	static int sqliteProcessJoin(Parse pParse, Select p){
sl@0	330	SrcList pSrc; / All tables in the FROM clause */
sl@0	331	int i, j; /* Loop counters */
sl@0	332	struct SrcList_item pLeft; / Left table being joined */
sl@0	333	struct SrcList_item pRight; / Right table being joined */
sl@0	334
sl@0	335	pSrc = p->pSrc;
sl@0	336	pLeft = &pSrc->a[0];
sl@0	337	pRight = &pLeft[1];
sl@0	338	for(i=0; i<pSrc->nSrc-1; i++, pRight++, pLeft++){
sl@0	339	Table *pLeftTab = pLeft->pTab;
sl@0	340	Table *pRightTab = pRight->pTab;
sl@0	341	int isOuter;
sl@0	342
sl@0	343	if( pLeftTab==0 \|\| pRightTab==0 ) continue;
sl@0	344	isOuter = (pRight->jointype & JT_OUTER)!=0;
sl@0	345
sl@0	346	/* When the NATURAL keyword is present, add WHERE clause terms for
sl@0	347	** every column that the two tables have in common.
sl@0	348	*/
sl@0	349	if( pRight->jointype & JT_NATURAL ){
sl@0	350	if( pRight->pOn \|\| pRight->pUsing ){
sl@0	351	sqlite3ErrorMsg(pParse, "a NATURAL join may not have "
sl@0	352	"an ON or USING clause", 0);
sl@0	353	return 1;
sl@0	354	}
sl@0	355	for(j=0; j<pLeftTab->nCol; j++){
sl@0	356	char *zName = pLeftTab->aCol[j].zName;
sl@0	357	if( columnIndex(pRightTab, zName)>=0 ){
sl@0	358	addWhereTerm(pParse, zName, pLeftTab, pLeft->zAlias,
sl@0	359	pRightTab, pRight->zAlias,
sl@0	360	pRight->iCursor, &p->pWhere, isOuter);
sl@0	361
sl@0	362	}
sl@0	363	}
sl@0	364	}
sl@0	365
sl@0	366	/* Disallow both ON and USING clauses in the same join
sl@0	367	*/
sl@0	368	if( pRight->pOn && pRight->pUsing ){
sl@0	369	sqlite3ErrorMsg(pParse, "cannot have both ON and USING "
sl@0	370	"clauses in the same join");
sl@0	371	return 1;
sl@0	372	}
sl@0	373
sl@0	374	/* Add the ON clause to the end of the WHERE clause, connected by
sl@0	375	** an AND operator.
sl@0	376	*/
sl@0	377	if( pRight->pOn ){
sl@0	378	if( isOuter ) setJoinExpr(pRight->pOn, pRight->iCursor);
sl@0	379	p->pWhere = sqlite3ExprAnd(pParse->db, p->pWhere, pRight->pOn);
sl@0	380	pRight->pOn = 0;
sl@0	381	}
sl@0	382
sl@0	383	/* Create extra terms on the WHERE clause for each column named
sl@0	384	** in the USING clause. Example: If the two tables to be joined are
sl@0	385	** A and B and the USING clause names X, Y, and Z, then add this
sl@0	386	** to the WHERE clause: A.X=B.X AND A.Y=B.Y AND A.Z=B.Z
sl@0	387	** Report an error if any column mentioned in the USING clause is
sl@0	388	** not contained in both tables to be joined.
sl@0	389	*/
sl@0	390	if( pRight->pUsing ){
sl@0	391	IdList *pList = pRight->pUsing;
sl@0	392	for(j=0; j<pList->nId; j++){
sl@0	393	char *zName = pList->a[j].zName;
sl@0	394	if( columnIndex(pLeftTab, zName)<0 \|\| columnIndex(pRightTab, zName)<0 ){
sl@0	395	sqlite3ErrorMsg(pParse, "cannot join using column %s - column "
sl@0	396	"not present in both tables", zName);
sl@0	397	return 1;
sl@0	398	}
sl@0	399	addWhereTerm(pParse, zName, pLeftTab, pLeft->zAlias,
sl@0	400	pRightTab, pRight->zAlias,
sl@0	401	pRight->iCursor, &p->pWhere, isOuter);
sl@0	402	}
sl@0	403	}
sl@0	404	}
sl@0	405	return 0;
sl@0	406	}
sl@0	407
sl@0	408	/*
sl@0	409	** Insert code into "v" that will push the record on the top of the
sl@0	410	** stack into the sorter.
sl@0	411	*/
sl@0	412	static void pushOntoSorter(
sl@0	413	Parse pParse, / Parser context */
sl@0	414	ExprList pOrderBy, / The ORDER BY clause */
sl@0	415	Select pSelect, / The whole SELECT statement */
sl@0	416	int regData /* Register holding data to be sorted */
sl@0	417	){
sl@0	418	Vdbe *v = pParse->pVdbe;
sl@0	419	int nExpr = pOrderBy->nExpr;
sl@0	420	int regBase = sqlite3GetTempRange(pParse, nExpr+2);
sl@0	421	int regRecord = sqlite3GetTempReg(pParse);
sl@0	422	sqlite3ExprCodeExprList(pParse, pOrderBy, regBase, 0);
sl@0	423	sqlite3VdbeAddOp2(v, OP_Sequence, pOrderBy->iECursor, regBase+nExpr);
sl@0	424	sqlite3ExprCodeMove(pParse, regData, regBase+nExpr+1, 1);
sl@0	425	sqlite3VdbeAddOp3(v, OP_MakeRecord, regBase, nExpr + 2, regRecord);
sl@0	426	sqlite3VdbeAddOp2(v, OP_IdxInsert, pOrderBy->iECursor, regRecord);
sl@0	427	sqlite3ReleaseTempReg(pParse, regRecord);
sl@0	428	sqlite3ReleaseTempRange(pParse, regBase, nExpr+2);
sl@0	429	if( pSelect->iLimit ){
sl@0	430	int addr1, addr2;
sl@0	431	int iLimit;
sl@0	432	if( pSelect->iOffset ){
sl@0	433	iLimit = pSelect->iOffset+1;
sl@0	434	}else{
sl@0	435	iLimit = pSelect->iLimit;
sl@0	436	}
sl@0	437	addr1 = sqlite3VdbeAddOp1(v, OP_IfZero, iLimit);
sl@0	438	sqlite3VdbeAddOp2(v, OP_AddImm, iLimit, -1);
sl@0	439	addr2 = sqlite3VdbeAddOp0(v, OP_Goto);
sl@0	440	sqlite3VdbeJumpHere(v, addr1);
sl@0	441	sqlite3VdbeAddOp1(v, OP_Last, pOrderBy->iECursor);
sl@0	442	sqlite3VdbeAddOp1(v, OP_Delete, pOrderBy->iECursor);
sl@0	443	sqlite3VdbeJumpHere(v, addr2);
sl@0	444	pSelect->iLimit = 0;
sl@0	445	}
sl@0	446	}
sl@0	447
sl@0	448	/*
sl@0	449	** Add code to implement the OFFSET
sl@0	450	*/
sl@0	451	static void codeOffset(
sl@0	452	Vdbe v, / Generate code into this VM */
sl@0	453	Select p, / The SELECT statement being coded */
sl@0	454	int iContinue /* Jump here to skip the current record */
sl@0	455	){
sl@0	456	if( p->iOffset && iContinue!=0 ){
sl@0	457	int addr;
sl@0	458	sqlite3VdbeAddOp2(v, OP_AddImm, p->iOffset, -1);
sl@0	459	addr = sqlite3VdbeAddOp1(v, OP_IfNeg, p->iOffset);
sl@0	460	sqlite3VdbeAddOp2(v, OP_Goto, 0, iContinue);
sl@0	461	VdbeComment((v, "skip OFFSET records"));
sl@0	462	sqlite3VdbeJumpHere(v, addr);
sl@0	463	}
sl@0	464	}
sl@0	465
sl@0	466	/*
sl@0	467	** Add code that will check to make sure the N registers starting at iMem
sl@0	468	** form a distinct entry. iTab is a sorting index that holds previously
sl@0	469	** seen combinations of the N values. A new entry is made in iTab
sl@0	470	** if the current N values are new.
sl@0	471	**
sl@0	472	** A jump to addrRepeat is made and the N+1 values are popped from the
sl@0	473	** stack if the top N elements are not distinct.
sl@0	474	*/
sl@0	475	static void codeDistinct(
sl@0	476	Parse pParse, / Parsing and code generating context */
sl@0	477	int iTab, /* A sorting index used to test for distinctness */
sl@0	478	int addrRepeat, /* Jump to here if not distinct */
sl@0	479	int N, /* Number of elements */
sl@0	480	int iMem /* First element */
sl@0	481	){
sl@0	482	Vdbe *v;
sl@0	483	int r1;
sl@0	484
sl@0	485	v = pParse->pVdbe;
sl@0	486	r1 = sqlite3GetTempReg(pParse);
sl@0	487	sqlite3VdbeAddOp3(v, OP_MakeRecord, iMem, N, r1);
sl@0	488	sqlite3VdbeAddOp3(v, OP_Found, iTab, addrRepeat, r1);
sl@0	489	sqlite3VdbeAddOp2(v, OP_IdxInsert, iTab, r1);
sl@0	490	sqlite3ReleaseTempReg(pParse, r1);
sl@0	491	}
sl@0	492
sl@0	493	/*
sl@0	494	** Generate an error message when a SELECT is used within a subexpression
sl@0	495	** (example: "a IN (SELECT * FROM table)") but it has more than 1 result
sl@0	496	** column. We do this in a subroutine because the error occurs in multiple
sl@0	497	** places.
sl@0	498	*/
sl@0	499	static int checkForMultiColumnSelectError(
sl@0	500	Parse pParse, / Parse context. */
sl@0	501	SelectDest pDest, / Destination of SELECT results */
sl@0	502	int nExpr /* Number of result columns returned by SELECT */
sl@0	503	){
sl@0	504	int eDest = pDest->eDest;
sl@0	505	if( nExpr>1 && (eDest==SRT_Mem \|\| eDest==SRT_Set) ){
sl@0	506	sqlite3ErrorMsg(pParse, "only a single result allowed for "
sl@0	507	"a SELECT that is part of an expression");
sl@0	508	return 1;
sl@0	509	}else{
sl@0	510	return 0;
sl@0	511	}
sl@0	512	}
sl@0	513
sl@0	514	/*
sl@0	515	** This routine generates the code for the inside of the inner loop
sl@0	516	** of a SELECT.
sl@0	517	**
sl@0	518	** If srcTab and nColumn are both zero, then the pEList expressions
sl@0	519	** are evaluated in order to get the data for this row. If nColumn>0
sl@0	520	** then data is pulled from srcTab and pEList is used only to get the
sl@0	521	** datatypes for each column.
sl@0	522	*/
sl@0	523	static void selectInnerLoop(
sl@0	524	Parse pParse, / The parser context */
sl@0	525	Select p, / The complete select statement being coded */
sl@0	526	ExprList pEList, / List of values being extracted */
sl@0	527	int srcTab, /* Pull data from this table */
sl@0	528	int nColumn, /* Number of columns in the source table */
sl@0	529	ExprList pOrderBy, / If not NULL, sort results using this key */
sl@0	530	int distinct, /* If >=0, make sure results are distinct */
sl@0	531	SelectDest pDest, / How to dispose of the results */
sl@0	532	int iContinue, /* Jump here to continue with next row */
sl@0	533	int iBreak /* Jump here to break out of the inner loop */
sl@0	534	){
sl@0	535	Vdbe *v = pParse->pVdbe;
sl@0	536	int i;
sl@0	537	int hasDistinct; /* True if the DISTINCT keyword is present */
sl@0	538	int regResult; /* Start of memory holding result set */
sl@0	539	int eDest = pDest->eDest; /* How to dispose of results */
sl@0	540	int iParm = pDest->iParm; /* First argument to disposal method */
sl@0	541	int nResultCol; /* Number of result columns */
sl@0	542
sl@0	543	if( v==0 ) return;
sl@0	544	assert( pEList!=0 );
sl@0	545	hasDistinct = distinct>=0;
sl@0	546	if( pOrderBy==0 && !hasDistinct ){
sl@0	547	codeOffset(v, p, iContinue);
sl@0	548	}
sl@0	549
sl@0	550	/* Pull the requested columns.
sl@0	551	*/
sl@0	552	if( nColumn>0 ){
sl@0	553	nResultCol = nColumn;
sl@0	554	}else{
sl@0	555	nResultCol = pEList->nExpr;
sl@0	556	}
sl@0	557	if( pDest->iMem==0 ){
sl@0	558	pDest->iMem = pParse->nMem+1;
sl@0	559	pDest->nMem = nResultCol;
sl@0	560	pParse->nMem += nResultCol;
sl@0	561	}else if( pDest->nMem!=nResultCol ){
sl@0	562	/* This happens when two SELECTs of a compound SELECT have differing
sl@0	563	** numbers of result columns. The error message will be generated by
sl@0	564	** a higher-level routine. */
sl@0	565	return;
sl@0	566	}
sl@0	567	regResult = pDest->iMem;
sl@0	568	if( nColumn>0 ){
sl@0	569	for(i=0; i<nColumn; i++){
sl@0	570	sqlite3VdbeAddOp3(v, OP_Column, srcTab, i, regResult+i);
sl@0	571	}
sl@0	572	}else if( eDest!=SRT_Exists ){
sl@0	573	/* If the destination is an EXISTS(...) expression, the actual
sl@0	574	** values returned by the SELECT are not required.
sl@0	575	*/
sl@0	576	sqlite3ExprCodeExprList(pParse, pEList, regResult, eDest==SRT_Callback);
sl@0	577	}
sl@0	578	nColumn = nResultCol;
sl@0	579
sl@0	580	/* If the DISTINCT keyword was present on the SELECT statement
sl@0	581	** and this row has been seen before, then do not make this row
sl@0	582	** part of the result.
sl@0	583	*/
sl@0	584	if( hasDistinct ){
sl@0	585	assert( pEList!=0 );
sl@0	586	assert( pEList->nExpr==nColumn );
sl@0	587	codeDistinct(pParse, distinct, iContinue, nColumn, regResult);
sl@0	588	if( pOrderBy==0 ){
sl@0	589	codeOffset(v, p, iContinue);
sl@0	590	}
sl@0	591	}
sl@0	592
sl@0	593	if( checkForMultiColumnSelectError(pParse, pDest, pEList->nExpr) ){
sl@0	594	return;
sl@0	595	}
sl@0	596
sl@0	597	switch( eDest ){
sl@0	598	/* In this mode, write each query result to the key of the temporary
sl@0	599	** table iParm.
sl@0	600	*/
sl@0	601	#ifndef SQLITE_OMIT_COMPOUND_SELECT
sl@0	602	case SRT_Union: {
sl@0	603	int r1;
sl@0	604	r1 = sqlite3GetTempReg(pParse);
sl@0	605	sqlite3VdbeAddOp3(v, OP_MakeRecord, regResult, nColumn, r1);
sl@0	606	sqlite3VdbeAddOp2(v, OP_IdxInsert, iParm, r1);
sl@0	607	sqlite3ReleaseTempReg(pParse, r1);
sl@0	608	break;
sl@0	609	}
sl@0	610
sl@0	611	/* Construct a record from the query result, but instead of
sl@0	612	** saving that record, use it as a key to delete elements from
sl@0	613	** the temporary table iParm.
sl@0	614	*/
sl@0	615	case SRT_Except: {
sl@0	616	sqlite3VdbeAddOp3(v, OP_IdxDelete, iParm, regResult, nColumn);
sl@0	617	break;
sl@0	618	}
sl@0	619	#endif
sl@0	620
sl@0	621	/* Store the result as data using a unique key.
sl@0	622	*/
sl@0	623	case SRT_Table:
sl@0	624	case SRT_EphemTab: {
sl@0	625	int r1 = sqlite3GetTempReg(pParse);
sl@0	626	sqlite3VdbeAddOp3(v, OP_MakeRecord, regResult, nColumn, r1);
sl@0	627	if( pOrderBy ){
sl@0	628	pushOntoSorter(pParse, pOrderBy, p, r1);
sl@0	629	}else{
sl@0	630	int r2 = sqlite3GetTempReg(pParse);
sl@0	631	sqlite3VdbeAddOp2(v, OP_NewRowid, iParm, r2);
sl@0	632	sqlite3VdbeAddOp3(v, OP_Insert, iParm, r1, r2);
sl@0	633	sqlite3VdbeChangeP5(v, OPFLAG_APPEND);
sl@0	634	sqlite3ReleaseTempReg(pParse, r2);
sl@0	635	}
sl@0	636	sqlite3ReleaseTempReg(pParse, r1);
sl@0	637	break;
sl@0	638	}
sl@0	639
sl@0	640	#ifndef SQLITE_OMIT_SUBQUERY
sl@0	641	/* If we are creating a set for an "expr IN (SELECT ...)" construct,
sl@0	642	** then there should be a single item on the stack. Write this
sl@0	643	** item into the set table with bogus data.
sl@0	644	*/
sl@0	645	case SRT_Set: {
sl@0	646	assert( nColumn==1 );
sl@0	647	p->affinity = sqlite3CompareAffinity(pEList->a[0].pExpr, pDest->affinity);
sl@0	648	if( pOrderBy ){
sl@0	649	/* At first glance you would think we could optimize out the
sl@0	650	** ORDER BY in this case since the order of entries in the set
sl@0	651	** does not matter. But there might be a LIMIT clause, in which
sl@0	652	** case the order does matter */
sl@0	653	pushOntoSorter(pParse, pOrderBy, p, regResult);
sl@0	654	}else{
sl@0	655	int r1 = sqlite3GetTempReg(pParse);
sl@0	656	sqlite3VdbeAddOp4(v, OP_MakeRecord, regResult, 1, r1, &p->affinity, 1);
sl@0	657	sqlite3ExprCacheAffinityChange(pParse, regResult, 1);
sl@0	658	sqlite3VdbeAddOp2(v, OP_IdxInsert, iParm, r1);
sl@0	659	sqlite3ReleaseTempReg(pParse, r1);
sl@0	660	}
sl@0	661	break;
sl@0	662	}
sl@0	663
sl@0	664	/* If any row exist in the result set, record that fact and abort.
sl@0	665	*/
sl@0	666	case SRT_Exists: {
sl@0	667	sqlite3VdbeAddOp2(v, OP_Integer, 1, iParm);
sl@0	668	/* The LIMIT clause will terminate the loop for us */
sl@0	669	break;
sl@0	670	}
sl@0	671
sl@0	672	/* If this is a scalar select that is part of an expression, then
sl@0	673	** store the results in the appropriate memory cell and break out
sl@0	674	** of the scan loop.
sl@0	675	*/
sl@0	676	case SRT_Mem: {
sl@0	677	assert( nColumn==1 );
sl@0	678	if( pOrderBy ){
sl@0	679	pushOntoSorter(pParse, pOrderBy, p, regResult);
sl@0	680	}else{
sl@0	681	sqlite3ExprCodeMove(pParse, regResult, iParm, 1);
sl@0	682	/* The LIMIT clause will jump out of the loop for us */
sl@0	683	}
sl@0	684	break;
sl@0	685	}
sl@0	686	#endif /* #ifndef SQLITE_OMIT_SUBQUERY */
sl@0	687
sl@0	688	/* Send the data to the callback function or to a subroutine. In the
sl@0	689	** case of a subroutine, the subroutine itself is responsible for
sl@0	690	** popping the data from the stack.
sl@0	691	*/
sl@0	692	case SRT_Coroutine:
sl@0	693	case SRT_Callback: {
sl@0	694	if( pOrderBy ){
sl@0	695	int r1 = sqlite3GetTempReg(pParse);
sl@0	696	sqlite3VdbeAddOp3(v, OP_MakeRecord, regResult, nColumn, r1);
sl@0	697	pushOntoSorter(pParse, pOrderBy, p, r1);
sl@0	698	sqlite3ReleaseTempReg(pParse, r1);
sl@0	699	}else if( eDest==SRT_Coroutine ){
sl@0	700	sqlite3VdbeAddOp1(v, OP_Yield, pDest->iParm);
sl@0	701	}else{
sl@0	702	sqlite3VdbeAddOp2(v, OP_ResultRow, regResult, nColumn);
sl@0	703	sqlite3ExprCacheAffinityChange(pParse, regResult, nColumn);
sl@0	704	}
sl@0	705	break;
sl@0	706	}
sl@0	707
sl@0	708	#if !defined(SQLITE_OMIT_TRIGGER)
sl@0	709	/* Discard the results. This is used for SELECT statements inside
sl@0	710	** the body of a TRIGGER. The purpose of such selects is to call
sl@0	711	** user-defined functions that have side effects. We do not care
sl@0	712	** about the actual results of the select.
sl@0	713	*/
sl@0	714	default: {
sl@0	715	assert( eDest==SRT_Discard );
sl@0	716	break;
sl@0	717	}
sl@0	718	#endif
sl@0	719	}
sl@0	720
sl@0	721	/* Jump to the end of the loop if the LIMIT is reached.
sl@0	722	*/
sl@0	723	if( p->iLimit ){
sl@0	724	assert( pOrderBy==0 ); /* If there is an ORDER BY, the call to
sl@0	725	** pushOntoSorter() would have cleared p->iLimit */
sl@0	726	sqlite3VdbeAddOp2(v, OP_AddImm, p->iLimit, -1);
sl@0	727	sqlite3VdbeAddOp2(v, OP_IfZero, p->iLimit, iBreak);
sl@0	728	}
sl@0	729	}
sl@0	730
sl@0	731	/*
sl@0	732	** Given an expression list, generate a KeyInfo structure that records
sl@0	733	** the collating sequence for each expression in that expression list.
sl@0	734	**
sl@0	735	** If the ExprList is an ORDER BY or GROUP BY clause then the resulting
sl@0	736	** KeyInfo structure is appropriate for initializing a virtual index to
sl@0	737	** implement that clause. If the ExprList is the result set of a SELECT
sl@0	738	** then the KeyInfo structure is appropriate for initializing a virtual
sl@0	739	** index to implement a DISTINCT test.
sl@0	740	**
sl@0	741	** Space to hold the KeyInfo structure is obtain from malloc. The calling
sl@0	742	** function is responsible for seeing that this structure is eventually
sl@0	743	** freed. Add the KeyInfo structure to the P4 field of an opcode using
sl@0	744	** P4_KEYINFO_HANDOFF is the usual way of dealing with this.
sl@0	745	*/
sl@0	746	static KeyInfo keyInfoFromExprList(Parse pParse, ExprList *pList){
sl@0	747	sqlite3 *db = pParse->db;
sl@0	748	int nExpr;
sl@0	749	KeyInfo *pInfo;
sl@0	750	struct ExprList_item *pItem;
sl@0	751	int i;
sl@0	752
sl@0	753	nExpr = pList->nExpr;
sl@0	754	pInfo = sqlite3DbMallocZero(db, sizeof(pInfo) + nExpr(sizeof(CollSeq*)+1) );
sl@0	755	if( pInfo ){
sl@0	756	pInfo->aSortOrder = (u8*)&pInfo->aColl[nExpr];
sl@0	757	pInfo->nField = nExpr;
sl@0	758	pInfo->enc = ENC(db);
sl@0	759	for(i=0, pItem=pList->a; i<nExpr; i++, pItem++){
sl@0	760	CollSeq *pColl;
sl@0	761	pColl = sqlite3ExprCollSeq(pParse, pItem->pExpr);
sl@0	762	if( !pColl ){
sl@0	763	pColl = db->pDfltColl;
sl@0	764	}
sl@0	765	pInfo->aColl[i] = pColl;
sl@0	766	pInfo->aSortOrder[i] = pItem->sortOrder;
sl@0	767	}
sl@0	768	}
sl@0	769	return pInfo;
sl@0	770	}
sl@0	771
sl@0	772
sl@0	773	/*
sl@0	774	** If the inner loop was generated using a non-null pOrderBy argument,
sl@0	775	** then the results were placed in a sorter. After the loop is terminated
sl@0	776	** we need to run the sorter and output the results. The following
sl@0	777	** routine generates the code needed to do that.
sl@0	778	*/
sl@0	779	static void generateSortTail(
sl@0	780	Parse pParse, / Parsing context */
sl@0	781	Select p, / The SELECT statement */
sl@0	782	Vdbe v, / Generate code into this VDBE */
sl@0	783	int nColumn, /* Number of columns of data */
sl@0	784	SelectDest pDest / Write the sorted results here */
sl@0	785	){
sl@0	786	int brk = sqlite3VdbeMakeLabel(v);
sl@0	787	int cont = sqlite3VdbeMakeLabel(v);
sl@0	788	int addr;
sl@0	789	int iTab;
sl@0	790	int pseudoTab = 0;
sl@0	791	ExprList *pOrderBy = p->pOrderBy;
sl@0	792
sl@0	793	int eDest = pDest->eDest;
sl@0	794	int iParm = pDest->iParm;
sl@0	795
sl@0	796	int regRow;
sl@0	797	int regRowid;
sl@0	798
sl@0	799	iTab = pOrderBy->iECursor;
sl@0	800	if( eDest==SRT_Callback \|\| eDest==SRT_Coroutine ){
sl@0	801	pseudoTab = pParse->nTab++;
sl@0	802	sqlite3VdbeAddOp2(v, OP_SetNumColumns, 0, nColumn);
sl@0	803	sqlite3VdbeAddOp2(v, OP_OpenPseudo, pseudoTab, eDest==SRT_Callback);
sl@0	804	}
sl@0	805	addr = 1 + sqlite3VdbeAddOp2(v, OP_Sort, iTab, brk);
sl@0	806	codeOffset(v, p, cont);
sl@0	807	regRow = sqlite3GetTempReg(pParse);
sl@0	808	regRowid = sqlite3GetTempReg(pParse);
sl@0	809	sqlite3VdbeAddOp3(v, OP_Column, iTab, pOrderBy->nExpr + 1, regRow);
sl@0	810	switch( eDest ){
sl@0	811	case SRT_Table:
sl@0	812	case SRT_EphemTab: {
sl@0	813	sqlite3VdbeAddOp2(v, OP_NewRowid, iParm, regRowid);
sl@0	814	sqlite3VdbeAddOp3(v, OP_Insert, iParm, regRow, regRowid);
sl@0	815	sqlite3VdbeChangeP5(v, OPFLAG_APPEND);
sl@0	816	break;
sl@0	817	}
sl@0	818	#ifndef SQLITE_OMIT_SUBQUERY
sl@0	819	case SRT_Set: {
sl@0	820	assert( nColumn==1 );
sl@0	821	sqlite3VdbeAddOp4(v, OP_MakeRecord, regRow, 1, regRowid, &p->affinity, 1);
sl@0	822	sqlite3ExprCacheAffinityChange(pParse, regRow, 1);
sl@0	823	sqlite3VdbeAddOp2(v, OP_IdxInsert, iParm, regRowid);
sl@0	824	break;
sl@0	825	}
sl@0	826	case SRT_Mem: {
sl@0	827	assert( nColumn==1 );
sl@0	828	sqlite3ExprCodeMove(pParse, regRow, iParm, 1);
sl@0	829	/* The LIMIT clause will terminate the loop for us */
sl@0	830	break;
sl@0	831	}
sl@0	832	#endif
sl@0	833	case SRT_Callback:
sl@0	834	case SRT_Coroutine: {
sl@0	835	int i;
sl@0	836	sqlite3VdbeAddOp2(v, OP_Integer, 1, regRowid);
sl@0	837	sqlite3VdbeAddOp3(v, OP_Insert, pseudoTab, regRow, regRowid);
sl@0	838	for(i=0; i<nColumn; i++){
sl@0	839	assert( regRow!=pDest->iMem+i );
sl@0	840	sqlite3VdbeAddOp3(v, OP_Column, pseudoTab, i, pDest->iMem+i);
sl@0	841	}
sl@0	842	if( eDest==SRT_Callback ){
sl@0	843	sqlite3VdbeAddOp2(v, OP_ResultRow, pDest->iMem, nColumn);
sl@0	844	sqlite3ExprCacheAffinityChange(pParse, pDest->iMem, nColumn);
sl@0	845	}else{
sl@0	846	sqlite3VdbeAddOp1(v, OP_Yield, pDest->iParm);
sl@0	847	}
sl@0	848	break;
sl@0	849	}
sl@0	850	default: {
sl@0	851	/* Do nothing */
sl@0	852	break;
sl@0	853	}
sl@0	854	}
sl@0	855	sqlite3ReleaseTempReg(pParse, regRow);
sl@0	856	sqlite3ReleaseTempReg(pParse, regRowid);
sl@0	857
sl@0	858	/* LIMIT has been implemented by the pushOntoSorter() routine.
sl@0	859	*/
sl@0	860	assert( p->iLimit==0 );
sl@0	861
sl@0	862	/* The bottom of the loop
sl@0	863	*/
sl@0	864	sqlite3VdbeResolveLabel(v, cont);
sl@0	865	sqlite3VdbeAddOp2(v, OP_Next, iTab, addr);
sl@0	866	sqlite3VdbeResolveLabel(v, brk);
sl@0	867	if( eDest==SRT_Callback \|\| eDest==SRT_Coroutine ){
sl@0	868	sqlite3VdbeAddOp2(v, OP_Close, pseudoTab, 0);
sl@0	869	}
sl@0	870
sl@0	871	}
sl@0	872
sl@0	873	/*
sl@0	874	** Return a pointer to a string containing the 'declaration type' of the
sl@0	875	** expression pExpr. The string may be treated as static by the caller.
sl@0	876	**
sl@0	877	** The declaration type is the exact datatype definition extracted from the
sl@0	878	** original CREATE TABLE statement if the expression is a column. The
sl@0	879	** declaration type for a ROWID field is INTEGER. Exactly when an expression
sl@0	880	** is considered a column can be complex in the presence of subqueries. The
sl@0	881	** result-set expression in all of the following SELECT statements is
sl@0	882	** considered a column by this function.
sl@0	883	**
sl@0	884	** SELECT col FROM tbl;
sl@0	885	** SELECT (SELECT col FROM tbl;
sl@0	886	** SELECT (SELECT col FROM tbl);
sl@0	887	** SELECT abc FROM (SELECT col AS abc FROM tbl);
sl@0	888	**
sl@0	889	** The declaration type for any expression other than a column is NULL.
sl@0	890	*/
sl@0	891	static const char *columnType(
sl@0	892	NameContext *pNC,
sl@0	893	Expr *pExpr,
sl@0	894	const char **pzOriginDb,
sl@0	895	const char **pzOriginTab,
sl@0	896	const char **pzOriginCol
sl@0	897	){
sl@0	898	char const *zType = 0;
sl@0	899	char const *zOriginDb = 0;
sl@0	900	char const *zOriginTab = 0;
sl@0	901	char const *zOriginCol = 0;
sl@0	902	int j;
sl@0	903	if( pExpr==0 \|\| pNC->pSrcList==0 ) return 0;
sl@0	904
sl@0	905	switch( pExpr->op ){
sl@0	906	case TK_AGG_COLUMN:
sl@0	907	case TK_COLUMN: {
sl@0	908	/* The expression is a column. Locate the table the column is being
sl@0	909	** extracted from in NameContext.pSrcList. This table may be real
sl@0	910	** database table or a subquery.
sl@0	911	*/
sl@0	912	Table pTab = 0; / Table structure column is extracted from */
sl@0	913	Select pS = 0; / Select the column is extracted from */
sl@0	914	int iCol = pExpr->iColumn; /* Index of column in pTab */
sl@0	915	while( pNC && !pTab ){
sl@0	916	SrcList *pTabList = pNC->pSrcList;
sl@0	917	for(j=0;j<pTabList->nSrc && pTabList->a[j].iCursor!=pExpr->iTable;j++);
sl@0	918	if( j<pTabList->nSrc ){
sl@0	919	pTab = pTabList->a[j].pTab;
sl@0	920	pS = pTabList->a[j].pSelect;
sl@0	921	}else{
sl@0	922	pNC = pNC->pNext;
sl@0	923	}
sl@0	924	}
sl@0	925
sl@0	926	if( pTab==0 ){
sl@0	927	/* FIX ME:
sl@0	928	** This can occurs if you have something like "SELECT new.x;" inside
sl@0	929	** a trigger. In other words, if you reference the special "new"
sl@0	930	** table in the result set of a select. We do not have a good way
sl@0	931	** to find the actual table type, so call it "TEXT". This is really
sl@0	932	** something of a bug, but I do not know how to fix it.
sl@0	933	**
sl@0	934	** This code does not produce the correct answer - it just prevents
sl@0	935	** a segfault. See ticket #1229.
sl@0	936	*/
sl@0	937	zType = "TEXT";
sl@0	938	break;
sl@0	939	}
sl@0	940
sl@0	941	assert( pTab );
sl@0	942	if( pS ){
sl@0	943	/* The "table" is actually a sub-select or a view in the FROM clause
sl@0	944	** of the SELECT statement. Return the declaration type and origin
sl@0	945	** data for the result-set column of the sub-select.
sl@0	946	*/
sl@0	947	if( iCol>=0 && iCol<pS->pEList->nExpr ){
sl@0	948	/* If iCol is less than zero, then the expression requests the
sl@0	949	** rowid of the sub-select or view. This expression is legal (see
sl@0	950	** test case misc2.2.2) - it always evaluates to NULL.
sl@0	951	*/
sl@0	952	NameContext sNC;
sl@0	953	Expr *p = pS->pEList->a[iCol].pExpr;
sl@0	954	sNC.pSrcList = pS->pSrc;
sl@0	955	sNC.pNext = 0;
sl@0	956	sNC.pParse = pNC->pParse;
sl@0	957	zType = columnType(&sNC, p, &zOriginDb, &zOriginTab, &zOriginCol);
sl@0	958	}
sl@0	959	}else if( pTab->pSchema ){
sl@0	960	/* A real table */
sl@0	961	assert( !pS );
sl@0	962	if( iCol<0 ) iCol = pTab->iPKey;
sl@0	963	assert( iCol==-1 \|\| (iCol>=0 && iCol<pTab->nCol) );
sl@0	964	if( iCol<0 ){
sl@0	965	zType = "INTEGER";
sl@0	966	zOriginCol = "rowid";
sl@0	967	}else{
sl@0	968	zType = pTab->aCol[iCol].zType;
sl@0	969	zOriginCol = pTab->aCol[iCol].zName;
sl@0	970	}
sl@0	971	zOriginTab = pTab->zName;
sl@0	972	if( pNC->pParse ){
sl@0	973	int iDb = sqlite3SchemaToIndex(pNC->pParse->db, pTab->pSchema);
sl@0	974	zOriginDb = pNC->pParse->db->aDb[iDb].zName;
sl@0	975	}
sl@0	976	}
sl@0	977	break;
sl@0	978	}
sl@0	979	#ifndef SQLITE_OMIT_SUBQUERY
sl@0	980	case TK_SELECT: {
sl@0	981	/* The expression is a sub-select. Return the declaration type and
sl@0	982	** origin info for the single column in the result set of the SELECT
sl@0	983	** statement.
sl@0	984	*/
sl@0	985	NameContext sNC;
sl@0	986	Select *pS = pExpr->pSelect;
sl@0	987	Expr *p = pS->pEList->a[0].pExpr;
sl@0	988	sNC.pSrcList = pS->pSrc;
sl@0	989	sNC.pNext = pNC;
sl@0	990	sNC.pParse = pNC->pParse;
sl@0	991	zType = columnType(&sNC, p, &zOriginDb, &zOriginTab, &zOriginCol);
sl@0	992	break;
sl@0	993	}
sl@0	994	#endif
sl@0	995	}
sl@0	996
sl@0	997	if( pzOriginDb ){
sl@0	998	assert( pzOriginTab && pzOriginCol );
sl@0	999	*pzOriginDb = zOriginDb;
sl@0	1000	*pzOriginTab = zOriginTab;
sl@0	1001	*pzOriginCol = zOriginCol;
sl@0	1002	}
sl@0	1003	return zType;
sl@0	1004	}
sl@0	1005
sl@0	1006	/*
sl@0	1007	** Generate code that will tell the VDBE the declaration types of columns
sl@0	1008	** in the result set.
sl@0	1009	*/
sl@0	1010	static void generateColumnTypes(
sl@0	1011	Parse pParse, / Parser context */
sl@0	1012	SrcList pTabList, / List of tables */
sl@0	1013	ExprList pEList / Expressions defining the result set */
sl@0	1014	){
sl@0	1015	#ifndef SQLITE_OMIT_DECLTYPE
sl@0	1016	Vdbe *v = pParse->pVdbe;
sl@0	1017	int i;
sl@0	1018	NameContext sNC;
sl@0	1019	sNC.pSrcList = pTabList;
sl@0	1020	sNC.pParse = pParse;
sl@0	1021	for(i=0; i<pEList->nExpr; i++){
sl@0	1022	Expr *p = pEList->a[i].pExpr;
sl@0	1023	const char *zType;
sl@0	1024	#ifdef SQLITE_ENABLE_COLUMN_METADATA
sl@0	1025	const char *zOrigDb = 0;
sl@0	1026	const char *zOrigTab = 0;
sl@0	1027	const char *zOrigCol = 0;
sl@0	1028	zType = columnType(&sNC, p, &zOrigDb, &zOrigTab, &zOrigCol);
sl@0	1029
sl@0	1030	/* The vdbe must make its own copy of the column-type and other
sl@0	1031	** column specific strings, in case the schema is reset before this
sl@0	1032	** virtual machine is deleted.
sl@0	1033	*/
sl@0	1034	sqlite3VdbeSetColName(v, i, COLNAME_DATABASE, zOrigDb, P4_TRANSIENT);
sl@0	1035	sqlite3VdbeSetColName(v, i, COLNAME_TABLE, zOrigTab, P4_TRANSIENT);
sl@0	1036	sqlite3VdbeSetColName(v, i, COLNAME_COLUMN, zOrigCol, P4_TRANSIENT);
sl@0	1037	#else
sl@0	1038	zType = columnType(&sNC, p, 0, 0, 0);
sl@0	1039	#endif
sl@0	1040	sqlite3VdbeSetColName(v, i, COLNAME_DECLTYPE, zType, P4_TRANSIENT);
sl@0	1041	}
sl@0	1042	#endif /* SQLITE_OMIT_DECLTYPE */
sl@0	1043	}
sl@0	1044
sl@0	1045	/*
sl@0	1046	** Generate code that will tell the VDBE the names of columns
sl@0	1047	** in the result set. This information is used to provide the
sl@0	1048	** azCol[] values in the callback.
sl@0	1049	*/
sl@0	1050	static void generateColumnNames(
sl@0	1051	Parse pParse, / Parser context */
sl@0	1052	SrcList pTabList, / List of tables */
sl@0	1053	ExprList pEList / Expressions defining the result set */
sl@0	1054	){
sl@0	1055	Vdbe *v = pParse->pVdbe;
sl@0	1056	int i, j;
sl@0	1057	sqlite3 *db = pParse->db;
sl@0	1058	int fullNames, shortNames;
sl@0	1059
sl@0	1060	#ifndef SQLITE_OMIT_EXPLAIN
sl@0	1061	/* If this is an EXPLAIN, skip this step */
sl@0	1062	if( pParse->explain ){
sl@0	1063	return;
sl@0	1064	}
sl@0	1065	#endif
sl@0	1066
sl@0	1067	assert( v!=0 );
sl@0	1068	if( pParse->colNamesSet \|\| v==0 \|\| db->mallocFailed ) return;
sl@0	1069	pParse->colNamesSet = 1;
sl@0	1070	fullNames = (db->flags & SQLITE_FullColNames)!=0;
sl@0	1071	shortNames = (db->flags & SQLITE_ShortColNames)!=0;
sl@0	1072	sqlite3VdbeSetNumCols(v, pEList->nExpr);
sl@0	1073	for(i=0; i<pEList->nExpr; i++){
sl@0	1074	Expr *p;
sl@0	1075	p = pEList->a[i].pExpr;
sl@0	1076	if( p==0 ) continue;
sl@0	1077	if( pEList->a[i].zName ){
sl@0	1078	char *zName = pEList->a[i].zName;
sl@0	1079	sqlite3VdbeSetColName(v, i, COLNAME_NAME, zName, strlen(zName));
sl@0	1080	}else if( p->op==TK_COLUMN && pTabList ){
sl@0	1081	Table *pTab;
sl@0	1082	char *zCol;
sl@0	1083	int iCol = p->iColumn;
sl@0	1084	for(j=0; j<pTabList->nSrc && pTabList->a[j].iCursor!=p->iTable; j++){}
sl@0	1085	assert( j<pTabList->nSrc );
sl@0	1086	pTab = pTabList->a[j].pTab;
sl@0	1087	if( iCol<0 ) iCol = pTab->iPKey;
sl@0	1088	assert( iCol==-1 \|\| (iCol>=0 && iCol<pTab->nCol) );
sl@0	1089	if( iCol<0 ){
sl@0	1090	zCol = "rowid";
sl@0	1091	}else{
sl@0	1092	zCol = pTab->aCol[iCol].zName;
sl@0	1093	}
sl@0	1094	if( !shortNames && !fullNames ){
sl@0	1095	sqlite3VdbeSetColName(v, i, COLNAME_NAME, (char*)p->span.z, p->span.n);
sl@0	1096	}else if( fullNames \|\| (!shortNames && pTabList->nSrc>1) ){
sl@0	1097	char *zName = 0;
sl@0	1098	char *zTab;
sl@0	1099
sl@0	1100	zTab = pTabList->a[j].zAlias;
sl@0	1101	if( fullNames \|\| zTab==0 ) zTab = pTab->zName;
sl@0	1102	zName = sqlite3MPrintf(db, "%s.%s", zTab, zCol);
sl@0	1103	sqlite3VdbeSetColName(v, i, COLNAME_NAME, zName, P4_DYNAMIC);
sl@0	1104	}else{
sl@0	1105	sqlite3VdbeSetColName(v, i, COLNAME_NAME, zCol, strlen(zCol));
sl@0	1106	}
sl@0	1107	}else{
sl@0	1108	sqlite3VdbeSetColName(v, i, COLNAME_NAME, (char*)p->span.z, p->span.n);
sl@0	1109	}
sl@0	1110	}
sl@0	1111	generateColumnTypes(pParse, pTabList, pEList);
sl@0	1112	}
sl@0	1113
sl@0	1114	#ifndef SQLITE_OMIT_COMPOUND_SELECT
sl@0	1115	/*
sl@0	1116	** Name of the connection operator, used for error messages.
sl@0	1117	*/
sl@0	1118	static const char *selectOpName(int id){
sl@0	1119	char *z;
sl@0	1120	switch( id ){
sl@0	1121	case TK_ALL: z = "UNION ALL"; break;
sl@0	1122	case TK_INTERSECT: z = "INTERSECT"; break;
sl@0	1123	case TK_EXCEPT: z = "EXCEPT"; break;
sl@0	1124	default: z = "UNION"; break;
sl@0	1125	}
sl@0	1126	return z;
sl@0	1127	}
sl@0	1128	#endif /* SQLITE_OMIT_COMPOUND_SELECT */
sl@0	1129
sl@0	1130	/*
sl@0	1131	** Forward declaration
sl@0	1132	*/
sl@0	1133	static int prepSelectStmt(Parse, Select);
sl@0	1134
sl@0	1135	/*
sl@0	1136	** Given a SELECT statement, generate a Table structure that describes
sl@0	1137	** the result set of that SELECT.
sl@0	1138	*/
sl@0	1139	Table sqlite3ResultSetOfSelect(Parse pParse, char zTabName, Select pSelect){
sl@0	1140	Table *pTab;
sl@0	1141	int i, j, rc;
sl@0	1142	ExprList *pEList;
sl@0	1143	Column aCol, pCol;
sl@0	1144	sqlite3 *db = pParse->db;
sl@0	1145	int savedFlags;
sl@0	1146
sl@0	1147	savedFlags = db->flags;
sl@0	1148	db->flags &= ~SQLITE_FullColNames;
sl@0	1149	db->flags \|= SQLITE_ShortColNames;
sl@0	1150	rc = sqlite3SelectResolve(pParse, pSelect, 0);
sl@0	1151	if( rc==SQLITE_OK ){
sl@0	1152	while( pSelect->pPrior ) pSelect = pSelect->pPrior;
sl@0	1153	rc = prepSelectStmt(pParse, pSelect);
sl@0	1154	if( rc==SQLITE_OK ){
sl@0	1155	rc = sqlite3SelectResolve(pParse, pSelect, 0);
sl@0	1156	}
sl@0	1157	}
sl@0	1158	db->flags = savedFlags;
sl@0	1159	if( rc ){
sl@0	1160	return 0;
sl@0	1161	}
sl@0	1162	pTab = sqlite3DbMallocZero(db, sizeof(Table) );
sl@0	1163	if( pTab==0 ){
sl@0	1164	return 0;
sl@0	1165	}
sl@0	1166	pTab->db = db;
sl@0	1167	pTab->nRef = 1;
sl@0	1168	pTab->zName = zTabName ? sqlite3DbStrDup(db, zTabName) : 0;
sl@0	1169	pEList = pSelect->pEList;
sl@0	1170	pTab->nCol = pEList->nExpr;
sl@0	1171	assert( pTab->nCol>0 );
sl@0	1172	pTab->aCol = aCol = sqlite3DbMallocZero(db, sizeof(pTab->aCol[0])*pTab->nCol);
sl@0	1173	testcase( aCol==0 );
sl@0	1174	for(i=0, pCol=aCol; i<pTab->nCol; i++, pCol++){
sl@0	1175	Expr *p;
sl@0	1176	char *zType;
sl@0	1177	char *zName;
sl@0	1178	int nName;
sl@0	1179	CollSeq *pColl;
sl@0	1180	int cnt;
sl@0	1181	NameContext sNC;
sl@0	1182
sl@0	1183	/* Get an appropriate name for the column
sl@0	1184	*/
sl@0	1185	p = pEList->a[i].pExpr;
sl@0	1186	assert( p->pRight==0 \|\| p->pRight->token.z==0 \|\| p->pRight->token.z[0]!=0 );
sl@0	1187	if( (zName = pEList->a[i].zName)!=0 ){
sl@0	1188	/* If the column contains an "AS <name>" phrase, use <name> as the name */
sl@0	1189	zName = sqlite3DbStrDup(db, zName);
sl@0	1190	}else if( p->op==TK_COLUMN && p->pTab ){
sl@0	1191	/* For columns use the column name name */
sl@0	1192	int iCol = p->iColumn;
sl@0	1193	if( iCol<0 ) iCol = p->pTab->iPKey;
sl@0	1194	zName = sqlite3MPrintf(db, "%s", p->pTab->aCol[iCol].zName);
sl@0	1195	}else{
sl@0	1196	/* Use the original text of the column expression as its name */
sl@0	1197	zName = sqlite3MPrintf(db, "%T", &p->span);
sl@0	1198	}
sl@0	1199	if( db->mallocFailed ){
sl@0	1200	sqlite3DbFree(db, zName);
sl@0	1201	break;
sl@0	1202	}
sl@0	1203	sqlite3Dequote(zName);
sl@0	1204
sl@0	1205	/* Make sure the column name is unique. If the name is not unique,
sl@0	1206	** append a integer to the name so that it becomes unique.
sl@0	1207	*/
sl@0	1208	nName = strlen(zName);
sl@0	1209	for(j=cnt=0; j<i; j++){
sl@0	1210	if( sqlite3StrICmp(aCol[j].zName, zName)==0 ){
sl@0	1211	char *zNewName;
sl@0	1212	zName[nName] = 0;
sl@0	1213	zNewName = sqlite3MPrintf(db, "%s:%d", zName, ++cnt);
sl@0	1214	sqlite3DbFree(db, zName);
sl@0	1215	zName = zNewName;
sl@0	1216	j = -1;
sl@0	1217	if( zName==0 ) break;
sl@0	1218	}
sl@0	1219	}
sl@0	1220	pCol->zName = zName;
sl@0	1221
sl@0	1222	/* Get the typename, type affinity, and collating sequence for the
sl@0	1223	** column.
sl@0	1224	*/
sl@0	1225	memset(&sNC, 0, sizeof(sNC));
sl@0	1226	sNC.pSrcList = pSelect->pSrc;
sl@0	1227	zType = sqlite3DbStrDup(db, columnType(&sNC, p, 0, 0, 0));
sl@0	1228	pCol->zType = zType;
sl@0	1229	pCol->affinity = sqlite3ExprAffinity(p);
sl@0	1230	pColl = sqlite3ExprCollSeq(pParse, p);
sl@0	1231	if( pColl ){
sl@0	1232	pCol->zColl = sqlite3DbStrDup(db, pColl->zName);
sl@0	1233	}
sl@0	1234	}
sl@0	1235	pTab->iPKey = -1;
sl@0	1236	if( db->mallocFailed ){
sl@0	1237	sqlite3DeleteTable(pTab);
sl@0	1238	return 0;
sl@0	1239	}
sl@0	1240	return pTab;
sl@0	1241	}
sl@0	1242
sl@0	1243	/*
sl@0	1244	** Prepare a SELECT statement for processing by doing the following
sl@0	1245	** things:
sl@0	1246	**
sl@0	1247	** (1) Make sure VDBE cursor numbers have been assigned to every
sl@0	1248	** element of the FROM clause.
sl@0	1249	**
sl@0	1250	** (2) Fill in the pTabList->a[].pTab fields in the SrcList that
sl@0	1251	** defines FROM clause. When views appear in the FROM clause,
sl@0	1252	** fill pTabList->a[].pSelect with a copy of the SELECT statement
sl@0	1253	** that implements the view. A copy is made of the view's SELECT
sl@0	1254	** statement so that we can freely modify or delete that statement
sl@0	1255	** without worrying about messing up the presistent representation
sl@0	1256	** of the view.
sl@0	1257	**
sl@0	1258	** (3) Add terms to the WHERE clause to accomodate the NATURAL keyword
sl@0	1259	** on joins and the ON and USING clause of joins.
sl@0	1260	**
sl@0	1261	** (4) Scan the list of columns in the result set (pEList) looking
sl@0	1262	** for instances of the "" operator or the TABLE. operator.
sl@0	1263	** If found, expand each "*" to be every column in every table
sl@0	1264	** and TABLE.* to be every column in TABLE.
sl@0	1265	**
sl@0	1266	** Return 0 on success. If there are problems, leave an error message
sl@0	1267	** in pParse and return non-zero.
sl@0	1268	*/
sl@0	1269	static int prepSelectStmt(Parse pParse, Select p){
sl@0	1270	int i, j, k, rc;
sl@0	1271	SrcList *pTabList;
sl@0	1272	ExprList *pEList;
sl@0	1273	struct SrcList_item *pFrom;
sl@0	1274	sqlite3 *db = pParse->db;
sl@0	1275
sl@0	1276	if( p==0 \|\| p->pSrc==0 \|\| db->mallocFailed ){
sl@0	1277	return 1;
sl@0	1278	}
sl@0	1279	pTabList = p->pSrc;
sl@0	1280	pEList = p->pEList;
sl@0	1281
sl@0	1282	/* Make sure cursor numbers have been assigned to all entries in
sl@0	1283	** the FROM clause of the SELECT statement.
sl@0	1284	*/
sl@0	1285	sqlite3SrcListAssignCursors(pParse, p->pSrc);
sl@0	1286
sl@0	1287	/* Look up every table named in the FROM clause of the select. If
sl@0	1288	** an entry of the FROM clause is a subquery instead of a table or view,
sl@0	1289	** then create a transient table structure to describe the subquery.
sl@0	1290	*/
sl@0	1291	for(i=0, pFrom=pTabList->a; i<pTabList->nSrc; i++, pFrom++){
sl@0	1292	Table *pTab;
sl@0	1293	if( pFrom->pTab!=0 ){
sl@0	1294	/* This statement has already been prepared. There is no need
sl@0	1295	** to go further. */
sl@0	1296	assert( i==0 );
sl@0	1297	return 0;
sl@0	1298	}
sl@0	1299	if( pFrom->zName==0 ){
sl@0	1300	#ifndef SQLITE_OMIT_SUBQUERY
sl@0	1301	/* A sub-query in the FROM clause of a SELECT */
sl@0	1302	assert( pFrom->pSelect!=0 );
sl@0	1303	if( pFrom->zAlias==0 ){
sl@0	1304	pFrom->zAlias =
sl@0	1305	sqlite3MPrintf(db, "sqlite_subquery_%p_", (void*)pFrom->pSelect);
sl@0	1306	}
sl@0	1307	assert( pFrom->pTab==0 );
sl@0	1308	pFrom->pTab = pTab =
sl@0	1309	sqlite3ResultSetOfSelect(pParse, pFrom->zAlias, pFrom->pSelect);
sl@0	1310	if( pTab==0 ){
sl@0	1311	return 1;
sl@0	1312	}
sl@0	1313	/* The isEphem flag indicates that the Table structure has been
sl@0	1314	** dynamically allocated and may be freed at any time. In other words,
sl@0	1315	** pTab is not pointing to a persistent table structure that defines
sl@0	1316	** part of the schema. */
sl@0	1317	pTab->isEphem = 1;
sl@0	1318	#endif
sl@0	1319	}else{
sl@0	1320	/* An ordinary table or view name in the FROM clause */
sl@0	1321	assert( pFrom->pTab==0 );
sl@0	1322	pFrom->pTab = pTab =
sl@0	1323	sqlite3LocateTable(pParse,0,pFrom->zName,pFrom->zDatabase);
sl@0	1324	if( pTab==0 ){
sl@0	1325	return 1;
sl@0	1326	}
sl@0	1327	pTab->nRef++;
sl@0	1328	#if !defined(SQLITE_OMIT_VIEW) \|\| !defined (SQLITE_OMIT_VIRTUALTABLE)
sl@0	1329	if( pTab->pSelect \|\| IsVirtual(pTab) ){
sl@0	1330	/* We reach here if the named table is a really a view */
sl@0	1331	if( sqlite3ViewGetColumnNames(pParse, pTab) ){
sl@0	1332	return 1;
sl@0	1333	}
sl@0	1334	/* If pFrom->pSelect!=0 it means we are dealing with a
sl@0	1335	** view within a view. The SELECT structure has already been
sl@0	1336	** copied by the outer view so we can skip the copy step here
sl@0	1337	** in the inner view.
sl@0	1338	*/
sl@0	1339	if( pFrom->pSelect==0 ){
sl@0	1340	pFrom->pSelect = sqlite3SelectDup(db, pTab->pSelect);
sl@0	1341	}
sl@0	1342	}
sl@0	1343	#endif
sl@0	1344	}
sl@0	1345	}
sl@0	1346
sl@0	1347	/* Process NATURAL keywords, and ON and USING clauses of joins.
sl@0	1348	*/
sl@0	1349	if( sqliteProcessJoin(pParse, p) ) return 1;
sl@0	1350
sl@0	1351	/* For every "*" that occurs in the column list, insert the names of
sl@0	1352	** all columns in all tables. And for every TABLE.* insert the names
sl@0	1353	** of all columns in TABLE. The parser inserted a special expression
sl@0	1354	** with the TK_ALL operator for each "*" that it found in the column list.
sl@0	1355	** The following code just has to locate the TK_ALL expressions and expand
sl@0	1356	** each one to the list of all columns in all tables.
sl@0	1357	**
sl@0	1358	** The first loop just checks to see if there are any "*" operators
sl@0	1359	** that need expanding.
sl@0	1360	*/
sl@0	1361	for(k=0; k<pEList->nExpr; k++){
sl@0	1362	Expr *pE = pEList->a[k].pExpr;
sl@0	1363	if( pE->op==TK_ALL ) break;
sl@0	1364	if( pE->op==TK_DOT && pE->pRight && pE->pRight->op==TK_ALL
sl@0	1365	&& pE->pLeft && pE->pLeft->op==TK_ID ) break;
sl@0	1366	}
sl@0	1367	rc = 0;
sl@0	1368	if( k<pEList->nExpr ){
sl@0	1369	/*
sl@0	1370	** If we get here it means the result set contains one or more "*"
sl@0	1371	** operators that need to be expanded. Loop through each expression
sl@0	1372	** in the result set and expand them one by one.
sl@0	1373	*/
sl@0	1374	struct ExprList_item *a = pEList->a;
sl@0	1375	ExprList *pNew = 0;
sl@0	1376	int flags = pParse->db->flags;
sl@0	1377	int longNames = (flags & SQLITE_FullColNames)!=0
sl@0	1378	&& (flags & SQLITE_ShortColNames)==0;
sl@0	1379
sl@0	1380	for(k=0; k<pEList->nExpr; k++){
sl@0	1381	Expr *pE = a[k].pExpr;
sl@0	1382	if( pE->op!=TK_ALL &&
sl@0	1383	(pE->op!=TK_DOT \|\| pE->pRight==0 \|\| pE->pRight->op!=TK_ALL) ){
sl@0	1384	/* This particular expression does not need to be expanded.
sl@0	1385	*/
sl@0	1386	pNew = sqlite3ExprListAppend(pParse, pNew, a[k].pExpr, 0);
sl@0	1387	if( pNew ){
sl@0	1388	pNew->a[pNew->nExpr-1].zName = a[k].zName;
sl@0	1389	}else{
sl@0	1390	rc = 1;
sl@0	1391	}
sl@0	1392	a[k].pExpr = 0;
sl@0	1393	a[k].zName = 0;
sl@0	1394	}else{
sl@0	1395	/* This expression is a "" or a "TABLE." and needs to be
sl@0	1396	** expanded. */
sl@0	1397	int tableSeen = 0; /* Set to 1 when TABLE matches */
sl@0	1398	char zTName; / text of name of TABLE */
sl@0	1399	if( pE->op==TK_DOT && pE->pLeft ){
sl@0	1400	zTName = sqlite3NameFromToken(db, &pE->pLeft->token);
sl@0	1401	}else{
sl@0	1402	zTName = 0;
sl@0	1403	}
sl@0	1404	for(i=0, pFrom=pTabList->a; i<pTabList->nSrc; i++, pFrom++){
sl@0	1405	Table *pTab = pFrom->pTab;
sl@0	1406	char *zTabName = pFrom->zAlias;
sl@0	1407	if( zTabName==0 \|\| zTabName[0]==0 ){
sl@0	1408	zTabName = pTab->zName;
sl@0	1409	}
sl@0	1410	assert( zTabName );
sl@0	1411	if( zTName && sqlite3StrICmp(zTName, zTabName)!=0 ){
sl@0	1412	continue;
sl@0	1413	}
sl@0	1414	tableSeen = 1;
sl@0	1415	for(j=0; j<pTab->nCol; j++){
sl@0	1416	Expr pExpr, pRight;
sl@0	1417	char *zName = pTab->aCol[j].zName;
sl@0	1418
sl@0	1419	/* If a column is marked as 'hidden' (currently only possible
sl@0	1420	** for virtual tables), do not include it in the expanded
sl@0	1421	** result-set list.
sl@0	1422	*/
sl@0	1423	if( IsHiddenColumn(&pTab->aCol[j]) ){
sl@0	1424	assert(IsVirtual(pTab));
sl@0	1425	continue;
sl@0	1426	}
sl@0	1427
sl@0	1428	if( i>0 ){
sl@0	1429	struct SrcList_item *pLeft = &pTabList->a[i-1];
sl@0	1430	if( (pLeft[1].jointype & JT_NATURAL)!=0 &&
sl@0	1431	columnIndex(pLeft->pTab, zName)>=0 ){
sl@0	1432	/* In a NATURAL join, omit the join columns from the
sl@0	1433	** table on the right */
sl@0	1434	continue;
sl@0	1435	}
sl@0	1436	if( sqlite3IdListIndex(pLeft[1].pUsing, zName)>=0 ){
sl@0	1437	/* In a join with a USING clause, omit columns in the
sl@0	1438	** using clause from the table on the right. */
sl@0	1439	continue;
sl@0	1440	}
sl@0	1441	}
sl@0	1442	pRight = sqlite3PExpr(pParse, TK_ID, 0, 0, 0);
sl@0	1443	if( pRight==0 ) break;
sl@0	1444	setQuotedToken(pParse, &pRight->token, zName);
sl@0	1445	if( longNames \|\| pTabList->nSrc>1 ){
sl@0	1446	Expr *pLeft = sqlite3PExpr(pParse, TK_ID, 0, 0, 0);
sl@0	1447	pExpr = sqlite3PExpr(pParse, TK_DOT, pLeft, pRight, 0);
sl@0	1448	if( pExpr==0 ) break;
sl@0	1449	setQuotedToken(pParse, &pLeft->token, zTabName);
sl@0	1450	#if 1
sl@0	1451	setToken(&pExpr->span,
sl@0	1452	sqlite3MPrintf(db, "%s.%s", zTabName, zName));
sl@0	1453	pExpr->span.dyn = 1;
sl@0	1454	#else
sl@0	1455	pExpr->span = pRight->token;
sl@0	1456	pExpr->span.dyn = 0;
sl@0	1457	#endif
sl@0	1458	pExpr->token.z = 0;
sl@0	1459	pExpr->token.n = 0;
sl@0	1460	pExpr->token.dyn = 0;
sl@0	1461	}else{
sl@0	1462	pExpr = pRight;
sl@0	1463	pExpr->span = pExpr->token;
sl@0	1464	pExpr->span.dyn = 0;
sl@0	1465	}
sl@0	1466	if( longNames ){
sl@0	1467	pNew = sqlite3ExprListAppend(pParse, pNew, pExpr, &pExpr->span);
sl@0	1468	}else{
sl@0	1469	pNew = sqlite3ExprListAppend(pParse, pNew, pExpr, &pRight->token);
sl@0	1470	}
sl@0	1471	}
sl@0	1472	}
sl@0	1473	if( !tableSeen ){
sl@0	1474	if( zTName ){
sl@0	1475	sqlite3ErrorMsg(pParse, "no such table: %s", zTName);
sl@0	1476	}else{
sl@0	1477	sqlite3ErrorMsg(pParse, "no tables specified");
sl@0	1478	}
sl@0	1479	rc = 1;
sl@0	1480	}
sl@0	1481	sqlite3DbFree(db, zTName);
sl@0	1482	}
sl@0	1483	}
sl@0	1484	sqlite3ExprListDelete(db, pEList);
sl@0	1485	p->pEList = pNew;
sl@0	1486	}
sl@0	1487	#if SQLITE_MAX_COLUMN
sl@0	1488	if( p->pEList && p->pEList->nExpr>db->aLimit[SQLITE_LIMIT_COLUMN] ){
sl@0	1489	sqlite3ErrorMsg(pParse, "too many columns in result set");
sl@0	1490	rc = SQLITE_ERROR;
sl@0	1491	}
sl@0	1492	#endif
sl@0	1493	if( db->mallocFailed ){
sl@0	1494	rc = SQLITE_NOMEM;
sl@0	1495	}
sl@0	1496	return rc;
sl@0	1497	}
sl@0	1498
sl@0	1499	/*
sl@0	1500	** pE is a pointer to an expression which is a single term in
sl@0	1501	** ORDER BY or GROUP BY clause.
sl@0	1502	**
sl@0	1503	** At the point this routine is called, we already know that the
sl@0	1504	** ORDER BY term is not an integer index into the result set. That
sl@0	1505	** casee is handled by the calling routine.
sl@0	1506	**
sl@0	1507	** If pE is a well-formed expression and the SELECT statement
sl@0	1508	** is not compound, then return 0. This indicates to the
sl@0	1509	** caller that it should sort by the value of the ORDER BY
sl@0	1510	** expression.
sl@0	1511	**
sl@0	1512	** If the SELECT is compound, then attempt to match pE against
sl@0	1513	** result set columns in the left-most SELECT statement. Return
sl@0	1514	** the index i of the matching column, as an indication to the
sl@0	1515	** caller that it should sort by the i-th column. If there is
sl@0	1516	** no match, return -1 and leave an error message in pParse.
sl@0	1517	*/
sl@0	1518	static int matchOrderByTermToExprList(
sl@0	1519	Parse pParse, / Parsing context for error messages */
sl@0	1520	Select pSelect, / The SELECT statement with the ORDER BY clause */
sl@0	1521	Expr pE, / The specific ORDER BY term */
sl@0	1522	int idx, /* When ORDER BY term is this */
sl@0	1523	int isCompound, /* True if this is a compound SELECT */
sl@0	1524	u8 pHasAgg / True if expression contains aggregate functions */
sl@0	1525	){
sl@0	1526	int i; /* Loop counter */
sl@0	1527	ExprList pEList; / The columns of the result set */
sl@0	1528	NameContext nc; /* Name context for resolving pE */
sl@0	1529
sl@0	1530	assert( sqlite3ExprIsInteger(pE, &i)==0 );
sl@0	1531	pEList = pSelect->pEList;
sl@0	1532
sl@0	1533	/* If the term is a simple identifier that try to match that identifier
sl@0	1534	** against a column name in the result set.
sl@0	1535	*/
sl@0	1536	if( pE->op==TK_ID \|\| (pE->op==TK_STRING && pE->token.z[0]!='\'') ){
sl@0	1537	sqlite3 *db = pParse->db;
sl@0	1538	char *zCol = sqlite3NameFromToken(db, &pE->token);
sl@0	1539	if( zCol==0 ){
sl@0	1540	return -1;
sl@0	1541	}
sl@0	1542	for(i=0; i<pEList->nExpr; i++){
sl@0	1543	char *zAs = pEList->a[i].zName;
sl@0	1544	if( zAs!=0 && sqlite3StrICmp(zAs, zCol)==0 ){
sl@0	1545	sqlite3DbFree(db, zCol);
sl@0	1546	return i+1;
sl@0	1547	}
sl@0	1548	}
sl@0	1549	sqlite3DbFree(db, zCol);
sl@0	1550	}
sl@0	1551
sl@0	1552	/* Resolve all names in the ORDER BY term expression
sl@0	1553	*/
sl@0	1554	memset(&nc, 0, sizeof(nc));
sl@0	1555	nc.pParse = pParse;
sl@0	1556	nc.pSrcList = pSelect->pSrc;
sl@0	1557	nc.pEList = pEList;
sl@0	1558	nc.allowAgg = 1;
sl@0	1559	nc.nErr = 0;
sl@0	1560	if( sqlite3ExprResolveNames(&nc, pE) ){
sl@0	1561	if( isCompound ){
sl@0	1562	sqlite3ErrorClear(pParse);
sl@0	1563	return 0;
sl@0	1564	}else{
sl@0	1565	return -1;
sl@0	1566	}
sl@0	1567	}
sl@0	1568	if( nc.hasAgg && pHasAgg ){
sl@0	1569	*pHasAgg = 1;
sl@0	1570	}
sl@0	1571
sl@0	1572	/* For a compound SELECT, we need to try to match the ORDER BY
sl@0	1573	** expression against an expression in the result set
sl@0	1574	*/
sl@0	1575	if( isCompound ){
sl@0	1576	for(i=0; i<pEList->nExpr; i++){
sl@0	1577	if( sqlite3ExprCompare(pEList->a[i].pExpr, pE) ){
sl@0	1578	return i+1;
sl@0	1579	}
sl@0	1580	}
sl@0	1581	}
sl@0	1582	return 0;
sl@0	1583	}
sl@0	1584
sl@0	1585
sl@0	1586	/*
sl@0	1587	** Analyze and ORDER BY or GROUP BY clause in a simple SELECT statement.
sl@0	1588	** Return the number of errors seen.
sl@0	1589	**
sl@0	1590	** Every term of the ORDER BY or GROUP BY clause needs to be an
sl@0	1591	** expression. If any expression is an integer constant, then
sl@0	1592	** that expression is replaced by the corresponding
sl@0	1593	** expression from the result set.
sl@0	1594	*/
sl@0	1595	static int processOrderGroupBy(
sl@0	1596	Parse pParse, / Parsing context. Leave error messages here */
sl@0	1597	Select pSelect, / The SELECT statement containing the clause */
sl@0	1598	ExprList pOrderBy, / The ORDER BY or GROUP BY clause to be processed */
sl@0	1599	int isOrder, /* 1 for ORDER BY. 0 for GROUP BY */
sl@0	1600	u8 pHasAgg / Set to TRUE if any term contains an aggregate */
sl@0	1601	){
sl@0	1602	int i;
sl@0	1603	sqlite3 *db = pParse->db;
sl@0	1604	ExprList *pEList;
sl@0	1605
sl@0	1606	if( pOrderBy==0 \|\| pParse->db->mallocFailed ) return 0;
sl@0	1607	#if SQLITE_MAX_COLUMN
sl@0	1608	if( pOrderBy->nExpr>db->aLimit[SQLITE_LIMIT_COLUMN] ){
sl@0	1609	const char *zType = isOrder ? "ORDER" : "GROUP";
sl@0	1610	sqlite3ErrorMsg(pParse, "too many terms in %s BY clause", zType);
sl@0	1611	return 1;
sl@0	1612	}
sl@0	1613	#endif
sl@0	1614	pEList = pSelect->pEList;
sl@0	1615	if( pEList==0 ){
sl@0	1616	return 0;
sl@0	1617	}
sl@0	1618	for(i=0; i<pOrderBy->nExpr; i++){
sl@0	1619	int iCol;
sl@0	1620	Expr *pE = pOrderBy->a[i].pExpr;
sl@0	1621	if( sqlite3ExprIsInteger(pE, &iCol) ){
sl@0	1622	if( iCol<=0 \|\| iCol>pEList->nExpr ){
sl@0	1623	const char *zType = isOrder ? "ORDER" : "GROUP";
sl@0	1624	sqlite3ErrorMsg(pParse,
sl@0	1625	"%r %s BY term out of range - should be "
sl@0	1626	"between 1 and %d", i+1, zType, pEList->nExpr);
sl@0	1627	return 1;
sl@0	1628	}
sl@0	1629	}else{
sl@0	1630	iCol = matchOrderByTermToExprList(pParse, pSelect, pE, i+1, 0, pHasAgg);
sl@0	1631	if( iCol<0 ){
sl@0	1632	return 1;
sl@0	1633	}
sl@0	1634	}
sl@0	1635	if( iCol>0 ){
sl@0	1636	CollSeq *pColl = pE->pColl;
sl@0	1637	int flags = pE->flags & EP_ExpCollate;
sl@0	1638	sqlite3ExprDelete(db, pE);
sl@0	1639	pE = sqlite3ExprDup(db, pEList->a[iCol-1].pExpr);
sl@0	1640	pOrderBy->a[i].pExpr = pE;
sl@0	1641	if( pE && pColl && flags ){
sl@0	1642	pE->pColl = pColl;
sl@0	1643	pE->flags \|= flags;
sl@0	1644	}
sl@0	1645	}
sl@0	1646	}
sl@0	1647	return 0;
sl@0	1648	}
sl@0	1649
sl@0	1650	/*
sl@0	1651	** Analyze and ORDER BY or GROUP BY clause in a SELECT statement. Return
sl@0	1652	** the number of errors seen.
sl@0	1653	**
sl@0	1654	** If iTable>0 then make the N-th term of the ORDER BY clause refer to
sl@0	1655	** the N-th column of table iTable.
sl@0	1656	**
sl@0	1657	** If iTable==0 then transform each term of the ORDER BY clause to refer
sl@0	1658	** to a column of the result set by number.
sl@0	1659	*/
sl@0	1660	static int processCompoundOrderBy(
sl@0	1661	Parse pParse, / Parsing context. Leave error messages here */
sl@0	1662	Select pSelect / The SELECT statement containing the ORDER BY */
sl@0	1663	){
sl@0	1664	int i;
sl@0	1665	ExprList *pOrderBy;
sl@0	1666	ExprList *pEList;
sl@0	1667	sqlite3 *db;
sl@0	1668	int moreToDo = 1;
sl@0	1669
sl@0	1670	pOrderBy = pSelect->pOrderBy;
sl@0	1671	if( pOrderBy==0 ) return 0;
sl@0	1672	db = pParse->db;
sl@0	1673	#if SQLITE_MAX_COLUMN
sl@0	1674	if( pOrderBy->nExpr>db->aLimit[SQLITE_LIMIT_COLUMN] ){
sl@0	1675	sqlite3ErrorMsg(pParse, "too many terms in ORDER BY clause");
sl@0	1676	return 1;
sl@0	1677	}
sl@0	1678	#endif
sl@0	1679	for(i=0; i<pOrderBy->nExpr; i++){
sl@0	1680	pOrderBy->a[i].done = 0;
sl@0	1681	}
sl@0	1682	while( pSelect->pPrior ){
sl@0	1683	pSelect = pSelect->pPrior;
sl@0	1684	}
sl@0	1685	while( pSelect && moreToDo ){
sl@0	1686	moreToDo = 0;
sl@0	1687	pEList = pSelect->pEList;
sl@0	1688	if( pEList==0 ){
sl@0	1689	return 1;
sl@0	1690	}
sl@0	1691	for(i=0; i<pOrderBy->nExpr; i++){
sl@0	1692	int iCol = -1;
sl@0	1693	Expr pE, pDup;
sl@0	1694	if( pOrderBy->a[i].done ) continue;
sl@0	1695	pE = pOrderBy->a[i].pExpr;
sl@0	1696	if( sqlite3ExprIsInteger(pE, &iCol) ){
sl@0	1697	if( iCol<0 \|\| iCol>pEList->nExpr ){
sl@0	1698	sqlite3ErrorMsg(pParse,
sl@0	1699	"%r ORDER BY term out of range - should be "
sl@0	1700	"between 1 and %d", i+1, pEList->nExpr);
sl@0	1701	return 1;
sl@0	1702	}
sl@0	1703	}else{
sl@0	1704	pDup = sqlite3ExprDup(db, pE);
sl@0	1705	if( !db->mallocFailed ){
sl@0	1706	assert(pDup);
sl@0	1707	iCol = matchOrderByTermToExprList(pParse, pSelect, pDup, i+1, 1, 0);
sl@0	1708	}
sl@0	1709	sqlite3ExprDelete(db, pDup);
sl@0	1710	if( iCol<0 ){
sl@0	1711	return 1;
sl@0	1712	}
sl@0	1713	}
sl@0	1714	if( iCol>0 ){
sl@0	1715	pE->op = TK_INTEGER;
sl@0	1716	pE->flags \|= EP_IntValue;
sl@0	1717	pE->iTable = iCol;
sl@0	1718	pOrderBy->a[i].done = 1;
sl@0	1719	}else{
sl@0	1720	moreToDo = 1;
sl@0	1721	}
sl@0	1722	}
sl@0	1723	pSelect = pSelect->pNext;
sl@0	1724	}
sl@0	1725	for(i=0; i<pOrderBy->nExpr; i++){
sl@0	1726	if( pOrderBy->a[i].done==0 ){
sl@0	1727	sqlite3ErrorMsg(pParse, "%r ORDER BY term does not match any "
sl@0	1728	"column in the result set", i+1);
sl@0	1729	return 1;
sl@0	1730	}
sl@0	1731	}
sl@0	1732	return 0;
sl@0	1733	}
sl@0	1734
sl@0	1735	/*
sl@0	1736	** Get a VDBE for the given parser context. Create a new one if necessary.
sl@0	1737	** If an error occurs, return NULL and leave a message in pParse.
sl@0	1738	*/
sl@0	1739	Vdbe sqlite3GetVdbe(Parse pParse){
sl@0	1740	Vdbe *v = pParse->pVdbe;
sl@0	1741	if( v==0 ){
sl@0	1742	v = pParse->pVdbe = sqlite3VdbeCreate(pParse->db);
sl@0	1743	#ifndef SQLITE_OMIT_TRACE
sl@0	1744	if( v ){
sl@0	1745	sqlite3VdbeAddOp0(v, OP_Trace);
sl@0	1746	}
sl@0	1747	#endif
sl@0	1748	}
sl@0	1749	return v;
sl@0	1750	}
sl@0	1751
sl@0	1752
sl@0	1753	/*
sl@0	1754	** Compute the iLimit and iOffset fields of the SELECT based on the
sl@0	1755	** pLimit and pOffset expressions. pLimit and pOffset hold the expressions
sl@0	1756	** that appear in the original SQL statement after the LIMIT and OFFSET
sl@0	1757	** keywords. Or NULL if those keywords are omitted. iLimit and iOffset
sl@0	1758	** are the integer memory register numbers for counters used to compute
sl@0	1759	** the limit and offset. If there is no limit and/or offset, then
sl@0	1760	** iLimit and iOffset are negative.
sl@0	1761	**
sl@0	1762	** This routine changes the values of iLimit and iOffset only if
sl@0	1763	** a limit or offset is defined by pLimit and pOffset. iLimit and
sl@0	1764	** iOffset should have been preset to appropriate default values
sl@0	1765	** (usually but not always -1) prior to calling this routine.
sl@0	1766	** Only if pLimit!=0 or pOffset!=0 do the limit registers get
sl@0	1767	** redefined. The UNION ALL operator uses this property to force
sl@0	1768	** the reuse of the same limit and offset registers across multiple
sl@0	1769	** SELECT statements.
sl@0	1770	*/
sl@0	1771	static void computeLimitRegisters(Parse pParse, Select p, int iBreak){
sl@0	1772	Vdbe *v = 0;
sl@0	1773	int iLimit = 0;
sl@0	1774	int iOffset;
sl@0	1775	int addr1;
sl@0	1776	if( p->iLimit ) return;
sl@0	1777
sl@0	1778	/*
sl@0	1779	** "LIMIT -1" always shows all rows. There is some
sl@0	1780	** contraversy about what the correct behavior should be.
sl@0	1781	** The current implementation interprets "LIMIT 0" to mean
sl@0	1782	** no rows.
sl@0	1783	*/
sl@0	1784	if( p->pLimit ){
sl@0	1785	p->iLimit = iLimit = ++pParse->nMem;
sl@0	1786	v = sqlite3GetVdbe(pParse);
sl@0	1787	if( v==0 ) return;
sl@0	1788	sqlite3ExprCode(pParse, p->pLimit, iLimit);
sl@0	1789	sqlite3VdbeAddOp1(v, OP_MustBeInt, iLimit);
sl@0	1790	VdbeComment((v, "LIMIT counter"));
sl@0	1791	sqlite3VdbeAddOp2(v, OP_IfZero, iLimit, iBreak);
sl@0	1792	}
sl@0	1793	if( p->pOffset ){
sl@0	1794	p->iOffset = iOffset = ++pParse->nMem;
sl@0	1795	if( p->pLimit ){
sl@0	1796	pParse->nMem++; /* Allocate an extra register for limit+offset */
sl@0	1797	}
sl@0	1798	v = sqlite3GetVdbe(pParse);
sl@0	1799	if( v==0 ) return;
sl@0	1800	sqlite3ExprCode(pParse, p->pOffset, iOffset);
sl@0	1801	sqlite3VdbeAddOp1(v, OP_MustBeInt, iOffset);
sl@0	1802	VdbeComment((v, "OFFSET counter"));
sl@0	1803	addr1 = sqlite3VdbeAddOp1(v, OP_IfPos, iOffset);
sl@0	1804	sqlite3VdbeAddOp2(v, OP_Integer, 0, iOffset);
sl@0	1805	sqlite3VdbeJumpHere(v, addr1);
sl@0	1806	if( p->pLimit ){
sl@0	1807	sqlite3VdbeAddOp3(v, OP_Add, iLimit, iOffset, iOffset+1);
sl@0	1808	VdbeComment((v, "LIMIT+OFFSET"));
sl@0	1809	addr1 = sqlite3VdbeAddOp1(v, OP_IfPos, iLimit);
sl@0	1810	sqlite3VdbeAddOp2(v, OP_Integer, -1, iOffset+1);
sl@0	1811	sqlite3VdbeJumpHere(v, addr1);
sl@0	1812	}
sl@0	1813	}
sl@0	1814	}
sl@0	1815
sl@0	1816	#ifndef SQLITE_OMIT_COMPOUND_SELECT
sl@0	1817	/*
sl@0	1818	** Return the appropriate collating sequence for the iCol-th column of
sl@0	1819	** the result set for the compound-select statement "p". Return NULL if
sl@0	1820	** the column has no default collating sequence.
sl@0	1821	**
sl@0	1822	** The collating sequence for the compound select is taken from the
sl@0	1823	** left-most term of the select that has a collating sequence.
sl@0	1824	*/
sl@0	1825	static CollSeq multiSelectCollSeq(Parse pParse, Select *p, int iCol){
sl@0	1826	CollSeq *pRet;
sl@0	1827	if( p->pPrior ){
sl@0	1828	pRet = multiSelectCollSeq(pParse, p->pPrior, iCol);
sl@0	1829	}else{
sl@0	1830	pRet = 0;
sl@0	1831	}
sl@0	1832	if( pRet==0 ){
sl@0	1833	pRet = sqlite3ExprCollSeq(pParse, p->pEList->a[iCol].pExpr);
sl@0	1834	}
sl@0	1835	return pRet;
sl@0	1836	}
sl@0	1837	#endif /* SQLITE_OMIT_COMPOUND_SELECT */
sl@0	1838
sl@0	1839	/* Forward reference */
sl@0	1840	static int multiSelectOrderBy(
sl@0	1841	Parse pParse, / Parsing context */
sl@0	1842	Select p, / The right-most of SELECTs to be coded */
sl@0	1843	SelectDest pDest / What to do with query results */
sl@0	1844	);
sl@0	1845
sl@0	1846
sl@0	1847	#ifndef SQLITE_OMIT_COMPOUND_SELECT
sl@0	1848	/*
sl@0	1849	** This routine is called to process a compound query form from
sl@0	1850	** two or more separate queries using UNION, UNION ALL, EXCEPT, or
sl@0	1851	** INTERSECT
sl@0	1852	**
sl@0	1853	** "p" points to the right-most of the two queries. the query on the
sl@0	1854	** left is p->pPrior. The left query could also be a compound query
sl@0	1855	** in which case this routine will be called recursively.
sl@0	1856	**
sl@0	1857	** The results of the total query are to be written into a destination
sl@0	1858	** of type eDest with parameter iParm.
sl@0	1859	**
sl@0	1860	** Example 1: Consider a three-way compound SQL statement.
sl@0	1861	**
sl@0	1862	** SELECT a FROM t1 UNION SELECT b FROM t2 UNION SELECT c FROM t3
sl@0	1863	**
sl@0	1864	** This statement is parsed up as follows:
sl@0	1865	**
sl@0	1866	** SELECT c FROM t3
sl@0	1867	** \|
sl@0	1868	** `-----> SELECT b FROM t2
sl@0	1869	** \|
sl@0	1870	** `------> SELECT a FROM t1
sl@0	1871	**
sl@0	1872	** The arrows in the diagram above represent the Select.pPrior pointer.
sl@0	1873	** So if this routine is called with p equal to the t3 query, then
sl@0	1874	** pPrior will be the t2 query. p->op will be TK_UNION in this case.
sl@0	1875	**
sl@0	1876	** Notice that because of the way SQLite parses compound SELECTs, the
sl@0	1877	** individual selects always group from left to right.
sl@0	1878	*/
sl@0	1879	static int multiSelect(
sl@0	1880	Parse pParse, / Parsing context */
sl@0	1881	Select p, / The right-most of SELECTs to be coded */
sl@0	1882	SelectDest pDest / What to do with query results */
sl@0	1883	){
sl@0	1884	int rc = SQLITE_OK; /* Success code from a subroutine */
sl@0	1885	Select pPrior; / Another SELECT immediately to our left */
sl@0	1886	Vdbe v; / Generate code to this VDBE */
sl@0	1887	SelectDest dest; /* Alternative data destination */
sl@0	1888	Select pDelete = 0; / Chain of simple selects to delete */
sl@0	1889	sqlite3 db; / Database connection */
sl@0	1890
sl@0	1891	/* Make sure there is no ORDER BY or LIMIT clause on prior SELECTs. Only
sl@0	1892	** the last (right-most) SELECT in the series may have an ORDER BY or LIMIT.
sl@0	1893	*/
sl@0	1894	assert( p && p->pPrior ); /* Calling function guarantees this much */
sl@0	1895	db = pParse->db;
sl@0	1896	pPrior = p->pPrior;
sl@0	1897	assert( pPrior->pRightmost!=pPrior );
sl@0	1898	assert( pPrior->pRightmost==p->pRightmost );
sl@0	1899	if( pPrior->pOrderBy ){
sl@0	1900	sqlite3ErrorMsg(pParse,"ORDER BY clause should come after %s not before",
sl@0	1901	selectOpName(p->op));
sl@0	1902	rc = 1;
sl@0	1903	goto multi_select_end;
sl@0	1904	}
sl@0	1905	if( pPrior->pLimit ){
sl@0	1906	sqlite3ErrorMsg(pParse,"LIMIT clause should come after %s not before",
sl@0	1907	selectOpName(p->op));
sl@0	1908	rc = 1;
sl@0	1909	goto multi_select_end;
sl@0	1910	}
sl@0	1911
sl@0	1912	v = sqlite3GetVdbe(pParse);
sl@0	1913	assert( v!=0 ); /* The VDBE already created by calling function */
sl@0	1914
sl@0	1915	/* Create the destination temporary table if necessary
sl@0	1916	*/
sl@0	1917	dest = *pDest;
sl@0	1918	if( dest.eDest==SRT_EphemTab ){
sl@0	1919	assert( p->pEList );
sl@0	1920	sqlite3VdbeAddOp2(v, OP_OpenEphemeral, dest.iParm, p->pEList->nExpr);
sl@0	1921	dest.eDest = SRT_Table;
sl@0	1922	}
sl@0	1923
sl@0	1924	/* Make sure all SELECTs in the statement have the same number of elements
sl@0	1925	** in their result sets.
sl@0	1926	*/
sl@0	1927	assert( p->pEList && pPrior->pEList );
sl@0	1928	if( p->pEList->nExpr!=pPrior->pEList->nExpr ){
sl@0	1929	sqlite3ErrorMsg(pParse, "SELECTs to the left and right of %s"
sl@0	1930	" do not have the same number of result columns", selectOpName(p->op));
sl@0	1931	rc = 1;
sl@0	1932	goto multi_select_end;
sl@0	1933	}
sl@0	1934
sl@0	1935	/* Compound SELECTs that have an ORDER BY clause are handled separately.
sl@0	1936	*/
sl@0	1937	if( p->pOrderBy ){
sl@0	1938	return multiSelectOrderBy(pParse, p, pDest);
sl@0	1939	}
sl@0	1940
sl@0	1941	/* Generate code for the left and right SELECT statements.
sl@0	1942	*/
sl@0	1943	switch( p->op ){
sl@0	1944	case TK_ALL: {
sl@0	1945	int addr = 0;
sl@0	1946	assert( !pPrior->pLimit );
sl@0	1947	pPrior->pLimit = p->pLimit;
sl@0	1948	pPrior->pOffset = p->pOffset;
sl@0	1949	rc = sqlite3Select(pParse, pPrior, &dest, 0, 0, 0);
sl@0	1950	p->pLimit = 0;
sl@0	1951	p->pOffset = 0;
sl@0	1952	if( rc ){
sl@0	1953	goto multi_select_end;
sl@0	1954	}
sl@0	1955	p->pPrior = 0;
sl@0	1956	p->iLimit = pPrior->iLimit;
sl@0	1957	p->iOffset = pPrior->iOffset;
sl@0	1958	if( p->iLimit ){
sl@0	1959	addr = sqlite3VdbeAddOp1(v, OP_IfZero, p->iLimit);
sl@0	1960	VdbeComment((v, "Jump ahead if LIMIT reached"));
sl@0	1961	}
sl@0	1962	rc = sqlite3Select(pParse, p, &dest, 0, 0, 0);
sl@0	1963	pDelete = p->pPrior;
sl@0	1964	p->pPrior = pPrior;
sl@0	1965	if( rc ){
sl@0	1966	goto multi_select_end;
sl@0	1967	}
sl@0	1968	if( addr ){
sl@0	1969	sqlite3VdbeJumpHere(v, addr);
sl@0	1970	}
sl@0	1971	break;
sl@0	1972	}
sl@0	1973	case TK_EXCEPT:
sl@0	1974	case TK_UNION: {
sl@0	1975	int unionTab; /* Cursor number of the temporary table holding result */
sl@0	1976	int op = 0; /* One of the SRT_ operations to apply to self */
sl@0	1977	int priorOp; /* The SRT_ operation to apply to prior selects */
sl@0	1978	Expr pLimit, pOffset; /* Saved values of p->nLimit and p->nOffset */
sl@0	1979	int addr;
sl@0	1980	SelectDest uniondest;
sl@0	1981
sl@0	1982	priorOp = SRT_Union;
sl@0	1983	if( dest.eDest==priorOp && !p->pLimit && !p->pOffset ){
sl@0	1984	/* We can reuse a temporary table generated by a SELECT to our
sl@0	1985	** right.
sl@0	1986	*/
sl@0	1987	unionTab = dest.iParm;
sl@0	1988	}else{
sl@0	1989	/* We will need to create our own temporary table to hold the
sl@0	1990	** intermediate results.
sl@0	1991	*/
sl@0	1992	unionTab = pParse->nTab++;
sl@0	1993	assert( p->pOrderBy==0 );
sl@0	1994	addr = sqlite3VdbeAddOp2(v, OP_OpenEphemeral, unionTab, 0);
sl@0	1995	assert( p->addrOpenEphm[0] == -1 );
sl@0	1996	p->addrOpenEphm[0] = addr;
sl@0	1997	p->pRightmost->usesEphm = 1;
sl@0	1998	assert( p->pEList );
sl@0	1999	}
sl@0	2000
sl@0	2001	/* Code the SELECT statements to our left
sl@0	2002	*/
sl@0	2003	assert( !pPrior->pOrderBy );
sl@0	2004	sqlite3SelectDestInit(&uniondest, priorOp, unionTab);
sl@0	2005	rc = sqlite3Select(pParse, pPrior, &uniondest, 0, 0, 0);
sl@0	2006	if( rc ){
sl@0	2007	goto multi_select_end;
sl@0	2008	}
sl@0	2009
sl@0	2010	/* Code the current SELECT statement
sl@0	2011	*/
sl@0	2012	if( p->op==TK_EXCEPT ){
sl@0	2013	op = SRT_Except;
sl@0	2014	}else{
sl@0	2015	assert( p->op==TK_UNION );
sl@0	2016	op = SRT_Union;
sl@0	2017	}
sl@0	2018	p->pPrior = 0;
sl@0	2019	p->disallowOrderBy = 0;
sl@0	2020	pLimit = p->pLimit;
sl@0	2021	p->pLimit = 0;
sl@0	2022	pOffset = p->pOffset;
sl@0	2023	p->pOffset = 0;
sl@0	2024	uniondest.eDest = op;
sl@0	2025	rc = sqlite3Select(pParse, p, &uniondest, 0, 0, 0);
sl@0	2026	/* Query flattening in sqlite3Select() might refill p->pOrderBy.
sl@0	2027	** Be sure to delete p->pOrderBy, therefore, to avoid a memory leak. */
sl@0	2028	sqlite3ExprListDelete(db, p->pOrderBy);
sl@0	2029	pDelete = p->pPrior;
sl@0	2030	p->pPrior = pPrior;
sl@0	2031	p->pOrderBy = 0;
sl@0	2032	sqlite3ExprDelete(db, p->pLimit);
sl@0	2033	p->pLimit = pLimit;
sl@0	2034	p->pOffset = pOffset;
sl@0	2035	p->iLimit = 0;
sl@0	2036	p->iOffset = 0;
sl@0	2037	if( rc ){
sl@0	2038	goto multi_select_end;
sl@0	2039	}
sl@0	2040
sl@0	2041
sl@0	2042	/* Convert the data in the temporary table into whatever form
sl@0	2043	** it is that we currently need.
sl@0	2044	*/
sl@0	2045	if( dest.eDest!=priorOp \|\| unionTab!=dest.iParm ){
sl@0	2046	int iCont, iBreak, iStart;
sl@0	2047	assert( p->pEList );
sl@0	2048	if( dest.eDest==SRT_Callback ){
sl@0	2049	Select *pFirst = p;
sl@0	2050	while( pFirst->pPrior ) pFirst = pFirst->pPrior;
sl@0	2051	generateColumnNames(pParse, 0, pFirst->pEList);
sl@0	2052	}
sl@0	2053	iBreak = sqlite3VdbeMakeLabel(v);
sl@0	2054	iCont = sqlite3VdbeMakeLabel(v);
sl@0	2055	computeLimitRegisters(pParse, p, iBreak);
sl@0	2056	sqlite3VdbeAddOp2(v, OP_Rewind, unionTab, iBreak);
sl@0	2057	iStart = sqlite3VdbeCurrentAddr(v);
sl@0	2058	selectInnerLoop(pParse, p, p->pEList, unionTab, p->pEList->nExpr,
sl@0	2059	0, -1, &dest, iCont, iBreak);
sl@0	2060	sqlite3VdbeResolveLabel(v, iCont);
sl@0	2061	sqlite3VdbeAddOp2(v, OP_Next, unionTab, iStart);
sl@0	2062	sqlite3VdbeResolveLabel(v, iBreak);
sl@0	2063	sqlite3VdbeAddOp2(v, OP_Close, unionTab, 0);
sl@0	2064	}
sl@0	2065	break;
sl@0	2066	}
sl@0	2067	case TK_INTERSECT: {
sl@0	2068	int tab1, tab2;
sl@0	2069	int iCont, iBreak, iStart;
sl@0	2070	Expr pLimit, pOffset;
sl@0	2071	int addr;
sl@0	2072	SelectDest intersectdest;
sl@0	2073	int r1;
sl@0	2074
sl@0	2075	/* INTERSECT is different from the others since it requires
sl@0	2076	** two temporary tables. Hence it has its own case. Begin
sl@0	2077	** by allocating the tables we will need.
sl@0	2078	*/
sl@0	2079	tab1 = pParse->nTab++;
sl@0	2080	tab2 = pParse->nTab++;
sl@0	2081	assert( p->pOrderBy==0 );
sl@0	2082
sl@0	2083	addr = sqlite3VdbeAddOp2(v, OP_OpenEphemeral, tab1, 0);
sl@0	2084	assert( p->addrOpenEphm[0] == -1 );
sl@0	2085	p->addrOpenEphm[0] = addr;
sl@0	2086	p->pRightmost->usesEphm = 1;
sl@0	2087	assert( p->pEList );
sl@0	2088
sl@0	2089	/* Code the SELECTs to our left into temporary table "tab1".
sl@0	2090	*/
sl@0	2091	sqlite3SelectDestInit(&intersectdest, SRT_Union, tab1);
sl@0	2092	rc = sqlite3Select(pParse, pPrior, &intersectdest, 0, 0, 0);
sl@0	2093	if( rc ){
sl@0	2094	goto multi_select_end;
sl@0	2095	}
sl@0	2096
sl@0	2097	/* Code the current SELECT into temporary table "tab2"
sl@0	2098	*/
sl@0	2099	addr = sqlite3VdbeAddOp2(v, OP_OpenEphemeral, tab2, 0);
sl@0	2100	assert( p->addrOpenEphm[1] == -1 );
sl@0	2101	p->addrOpenEphm[1] = addr;
sl@0	2102	p->pPrior = 0;
sl@0	2103	pLimit = p->pLimit;
sl@0	2104	p->pLimit = 0;
sl@0	2105	pOffset = p->pOffset;
sl@0	2106	p->pOffset = 0;
sl@0	2107	intersectdest.iParm = tab2;
sl@0	2108	rc = sqlite3Select(pParse, p, &intersectdest, 0, 0, 0);
sl@0	2109	pDelete = p->pPrior;
sl@0	2110	p->pPrior = pPrior;
sl@0	2111	sqlite3ExprDelete(db, p->pLimit);
sl@0	2112	p->pLimit = pLimit;
sl@0	2113	p->pOffset = pOffset;
sl@0	2114	if( rc ){
sl@0	2115	goto multi_select_end;
sl@0	2116	}
sl@0	2117
sl@0	2118	/* Generate code to take the intersection of the two temporary
sl@0	2119	** tables.
sl@0	2120	*/
sl@0	2121	assert( p->pEList );
sl@0	2122	if( dest.eDest==SRT_Callback ){
sl@0	2123	Select *pFirst = p;
sl@0	2124	while( pFirst->pPrior ) pFirst = pFirst->pPrior;
sl@0	2125	generateColumnNames(pParse, 0, pFirst->pEList);
sl@0	2126	}
sl@0	2127	iBreak = sqlite3VdbeMakeLabel(v);
sl@0	2128	iCont = sqlite3VdbeMakeLabel(v);
sl@0	2129	computeLimitRegisters(pParse, p, iBreak);
sl@0	2130	sqlite3VdbeAddOp2(v, OP_Rewind, tab1, iBreak);
sl@0	2131	r1 = sqlite3GetTempReg(pParse);
sl@0	2132	iStart = sqlite3VdbeAddOp2(v, OP_RowKey, tab1, r1);
sl@0	2133	sqlite3VdbeAddOp3(v, OP_NotFound, tab2, iCont, r1);
sl@0	2134	sqlite3ReleaseTempReg(pParse, r1);
sl@0	2135	selectInnerLoop(pParse, p, p->pEList, tab1, p->pEList->nExpr,
sl@0	2136	0, -1, &dest, iCont, iBreak);
sl@0	2137	sqlite3VdbeResolveLabel(v, iCont);
sl@0	2138	sqlite3VdbeAddOp2(v, OP_Next, tab1, iStart);
sl@0	2139	sqlite3VdbeResolveLabel(v, iBreak);
sl@0	2140	sqlite3VdbeAddOp2(v, OP_Close, tab2, 0);
sl@0	2141	sqlite3VdbeAddOp2(v, OP_Close, tab1, 0);
sl@0	2142	break;
sl@0	2143	}
sl@0	2144	}
sl@0	2145
sl@0	2146	/* Compute collating sequences used by
sl@0	2147	** temporary tables needed to implement the compound select.
sl@0	2148	** Attach the KeyInfo structure to all temporary tables.
sl@0	2149	**
sl@0	2150	** This section is run by the right-most SELECT statement only.
sl@0	2151	** SELECT statements to the left always skip this part. The right-most
sl@0	2152	** SELECT might also skip this part if it has no ORDER BY clause and
sl@0	2153	** no temp tables are required.
sl@0	2154	*/
sl@0	2155	if( p->usesEphm ){
sl@0	2156	int i; /* Loop counter */
sl@0	2157	KeyInfo pKeyInfo; / Collating sequence for the result set */
sl@0	2158	Select pLoop; / For looping through SELECT statements */
sl@0	2159	CollSeq *apColl; / For looping through pKeyInfo->aColl[] */
sl@0	2160	int nCol; /* Number of columns in result set */
sl@0	2161
sl@0	2162	assert( p->pRightmost==p );
sl@0	2163	nCol = p->pEList->nExpr;
sl@0	2164	pKeyInfo = sqlite3DbMallocZero(db,
sl@0	2165	sizeof(pKeyInfo)+nCol(sizeof(CollSeq*) + 1));
sl@0	2166	if( !pKeyInfo ){
sl@0	2167	rc = SQLITE_NOMEM;
sl@0	2168	goto multi_select_end;
sl@0	2169	}
sl@0	2170
sl@0	2171	pKeyInfo->enc = ENC(db);
sl@0	2172	pKeyInfo->nField = nCol;
sl@0	2173
sl@0	2174	for(i=0, apColl=pKeyInfo->aColl; i<nCol; i++, apColl++){
sl@0	2175	*apColl = multiSelectCollSeq(pParse, p, i);
sl@0	2176	if( 0==*apColl ){
sl@0	2177	*apColl = db->pDfltColl;
sl@0	2178	}
sl@0	2179	}
sl@0	2180
sl@0	2181	for(pLoop=p; pLoop; pLoop=pLoop->pPrior){
sl@0	2182	for(i=0; i<2; i++){
sl@0	2183	int addr = pLoop->addrOpenEphm[i];
sl@0	2184	if( addr<0 ){
sl@0	2185	/* If [0] is unused then [1] is also unused. So we can
sl@0	2186	** always safely abort as soon as the first unused slot is found */
sl@0	2187	assert( pLoop->addrOpenEphm[1]<0 );
sl@0	2188	break;
sl@0	2189	}
sl@0	2190	sqlite3VdbeChangeP2(v, addr, nCol);
sl@0	2191	sqlite3VdbeChangeP4(v, addr, (char*)pKeyInfo, P4_KEYINFO);
sl@0	2192	pLoop->addrOpenEphm[i] = -1;
sl@0	2193	}
sl@0	2194	}
sl@0	2195	sqlite3DbFree(db, pKeyInfo);
sl@0	2196	}
sl@0	2197
sl@0	2198	multi_select_end:
sl@0	2199	pDest->iMem = dest.iMem;
sl@0	2200	pDest->nMem = dest.nMem;
sl@0	2201	sqlite3SelectDelete(db, pDelete);
sl@0	2202	return rc;
sl@0	2203	}
sl@0	2204	#endif /* SQLITE_OMIT_COMPOUND_SELECT */
sl@0	2205
sl@0	2206	/*
sl@0	2207	** Code an output subroutine for a coroutine implementation of a
sl@0	2208	** SELECT statment.
sl@0	2209	**
sl@0	2210	** The data to be output is contained in pIn->iMem. There are
sl@0	2211	** pIn->nMem columns to be output. pDest is where the output should
sl@0	2212	** be sent.
sl@0	2213	**
sl@0	2214	** regReturn is the number of the register holding the subroutine
sl@0	2215	** return address.
sl@0	2216	**
sl@0	2217	** If regPrev>0 then it is a the first register in a vector that
sl@0	2218	** records the previous output. mem[regPrev] is a flag that is false
sl@0	2219	** if there has been no previous output. If regPrev>0 then code is
sl@0	2220	** generated to suppress duplicates. pKeyInfo is used for comparing
sl@0	2221	** keys.
sl@0	2222	**
sl@0	2223	** If the LIMIT found in p->iLimit is reached, jump immediately to
sl@0	2224	** iBreak.
sl@0	2225	*/
sl@0	2226	static int generateOutputSubroutine(
sl@0	2227	Parse pParse, / Parsing context */
sl@0	2228	Select p, / The SELECT statement */
sl@0	2229	SelectDest pIn, / Coroutine supplying data */
sl@0	2230	SelectDest pDest, / Where to send the data */
sl@0	2231	int regReturn, /* The return address register */
sl@0	2232	int regPrev, /* Previous result register. No uniqueness if 0 */
sl@0	2233	KeyInfo pKeyInfo, / For comparing with previous entry */
sl@0	2234	int p4type, /* The p4 type for pKeyInfo */
sl@0	2235	int iBreak /* Jump here if we hit the LIMIT */
sl@0	2236	){
sl@0	2237	Vdbe *v = pParse->pVdbe;
sl@0	2238	int iContinue;
sl@0	2239	int addr;
sl@0	2240
sl@0	2241	addr = sqlite3VdbeCurrentAddr(v);
sl@0	2242	iContinue = sqlite3VdbeMakeLabel(v);
sl@0	2243
sl@0	2244	/* Suppress duplicates for UNION, EXCEPT, and INTERSECT
sl@0	2245	*/
sl@0	2246	if( regPrev ){
sl@0	2247	int j1, j2;
sl@0	2248	j1 = sqlite3VdbeAddOp1(v, OP_IfNot, regPrev);
sl@0	2249	j2 = sqlite3VdbeAddOp4(v, OP_Compare, pIn->iMem, regPrev+1, pIn->nMem,
sl@0	2250	(char*)pKeyInfo, p4type);
sl@0	2251	sqlite3VdbeAddOp3(v, OP_Jump, j2+2, iContinue, j2+2);
sl@0	2252	sqlite3VdbeJumpHere(v, j1);
sl@0	2253	sqlite3ExprCodeCopy(pParse, pIn->iMem, regPrev+1, pIn->nMem);
sl@0	2254	sqlite3VdbeAddOp2(v, OP_Integer, 1, regPrev);
sl@0	2255	}
sl@0	2256	if( pParse->db->mallocFailed ) return 0;
sl@0	2257
sl@0	2258	/* Suppress the the first OFFSET entries if there is an OFFSET clause
sl@0	2259	*/
sl@0	2260	codeOffset(v, p, iContinue);
sl@0	2261
sl@0	2262	switch( pDest->eDest ){
sl@0	2263	/* Store the result as data using a unique key.
sl@0	2264	*/
sl@0	2265	case SRT_Table:
sl@0	2266	case SRT_EphemTab: {
sl@0	2267	int r1 = sqlite3GetTempReg(pParse);
sl@0	2268	int r2 = sqlite3GetTempReg(pParse);
sl@0	2269	sqlite3VdbeAddOp3(v, OP_MakeRecord, pIn->iMem, pIn->nMem, r1);
sl@0	2270	sqlite3VdbeAddOp2(v, OP_NewRowid, pDest->iParm, r2);
sl@0	2271	sqlite3VdbeAddOp3(v, OP_Insert, pDest->iParm, r1, r2);
sl@0	2272	sqlite3VdbeChangeP5(v, OPFLAG_APPEND);
sl@0	2273	sqlite3ReleaseTempReg(pParse, r2);
sl@0	2274	sqlite3ReleaseTempReg(pParse, r1);
sl@0	2275	break;
sl@0	2276	}
sl@0	2277
sl@0	2278	#ifndef SQLITE_OMIT_SUBQUERY
sl@0	2279	/* If we are creating a set for an "expr IN (SELECT ...)" construct,
sl@0	2280	** then there should be a single item on the stack. Write this
sl@0	2281	** item into the set table with bogus data.
sl@0	2282	*/
sl@0	2283	case SRT_Set: {
sl@0	2284	int r1;
sl@0	2285	assert( pIn->nMem==1 );
sl@0	2286	p->affinity =
sl@0	2287	sqlite3CompareAffinity(p->pEList->a[0].pExpr, pDest->affinity);
sl@0	2288	r1 = sqlite3GetTempReg(pParse);
sl@0	2289	sqlite3VdbeAddOp4(v, OP_MakeRecord, pIn->iMem, 1, r1, &p->affinity, 1);
sl@0	2290	sqlite3ExprCacheAffinityChange(pParse, pIn->iMem, 1);
sl@0	2291	sqlite3VdbeAddOp2(v, OP_IdxInsert, pDest->iParm, r1);
sl@0	2292	sqlite3ReleaseTempReg(pParse, r1);
sl@0	2293	break;
sl@0	2294	}
sl@0	2295
sl@0	2296	#if 0 /* Never occurs on an ORDER BY query */
sl@0	2297	/* If any row exist in the result set, record that fact and abort.
sl@0	2298	*/
sl@0	2299	case SRT_Exists: {
sl@0	2300	sqlite3VdbeAddOp2(v, OP_Integer, 1, pDest->iParm);
sl@0	2301	/* The LIMIT clause will terminate the loop for us */
sl@0	2302	break;
sl@0	2303	}
sl@0	2304	#endif
sl@0	2305
sl@0	2306	/* If this is a scalar select that is part of an expression, then
sl@0	2307	** store the results in the appropriate memory cell and break out
sl@0	2308	** of the scan loop.
sl@0	2309	*/
sl@0	2310	case SRT_Mem: {
sl@0	2311	assert( pIn->nMem==1 );
sl@0	2312	sqlite3ExprCodeMove(pParse, pIn->iMem, pDest->iParm, 1);
sl@0	2313	/* The LIMIT clause will jump out of the loop for us */
sl@0	2314	break;
sl@0	2315	}
sl@0	2316	#endif /* #ifndef SQLITE_OMIT_SUBQUERY */
sl@0	2317
sl@0	2318	/* Send the data to the callback function or to a subroutine. In the
sl@0	2319	** case of a subroutine, the subroutine itself is responsible for
sl@0	2320	** popping the data from the stack.
sl@0	2321	*/
sl@0	2322	case SRT_Coroutine: {
sl@0	2323	if( pDest->iMem==0 ){
sl@0	2324	pDest->iMem = sqlite3GetTempRange(pParse, pIn->nMem);
sl@0	2325	pDest->nMem = pIn->nMem;
sl@0	2326	}
sl@0	2327	sqlite3ExprCodeMove(pParse, pIn->iMem, pDest->iMem, pDest->nMem);
sl@0	2328	sqlite3VdbeAddOp1(v, OP_Yield, pDest->iParm);
sl@0	2329	break;
sl@0	2330	}
sl@0	2331
sl@0	2332	case SRT_Callback: {
sl@0	2333	sqlite3VdbeAddOp2(v, OP_ResultRow, pIn->iMem, pIn->nMem);
sl@0	2334	sqlite3ExprCacheAffinityChange(pParse, pIn->iMem, pIn->nMem);
sl@0	2335	break;
sl@0	2336	}
sl@0	2337
sl@0	2338	#if !defined(SQLITE_OMIT_TRIGGER)
sl@0	2339	/* Discard the results. This is used for SELECT statements inside
sl@0	2340	** the body of a TRIGGER. The purpose of such selects is to call
sl@0	2341	** user-defined functions that have side effects. We do not care
sl@0	2342	** about the actual results of the select.
sl@0	2343	*/
sl@0	2344	default: {
sl@0	2345	break;
sl@0	2346	}
sl@0	2347	#endif
sl@0	2348	}
sl@0	2349
sl@0	2350	/* Jump to the end of the loop if the LIMIT is reached.
sl@0	2351	*/
sl@0	2352	if( p->iLimit ){
sl@0	2353	sqlite3VdbeAddOp2(v, OP_AddImm, p->iLimit, -1);
sl@0	2354	sqlite3VdbeAddOp2(v, OP_IfZero, p->iLimit, iBreak);
sl@0	2355	}
sl@0	2356
sl@0	2357	/* Generate the subroutine return
sl@0	2358	*/
sl@0	2359	sqlite3VdbeResolveLabel(v, iContinue);
sl@0	2360	sqlite3VdbeAddOp1(v, OP_Return, regReturn);
sl@0	2361
sl@0	2362	return addr;
sl@0	2363	}
sl@0	2364
sl@0	2365	/*
sl@0	2366	** Alternative compound select code generator for cases when there
sl@0	2367	** is an ORDER BY clause.
sl@0	2368	**
sl@0	2369	** We assume a query of the following form:
sl@0	2370	**
sl@0	2371	** <selectA> <operator> <selectB> ORDER BY <orderbylist>
sl@0	2372	**
sl@0	2373	** <operator> is one of UNION ALL, UNION, EXCEPT, or INTERSECT. The idea
sl@0	2374	** is to code both <selectA> and <selectB> with the ORDER BY clause as
sl@0	2375	** co-routines. Then run the co-routines in parallel and merge the results
sl@0	2376	** into the output. In addition to the two coroutines (called selectA and
sl@0	2377	** selectB) there are 7 subroutines:
sl@0	2378	**
sl@0	2379	** outA: Move the output of the selectA coroutine into the output
sl@0	2380	** of the compound query.
sl@0	2381	**
sl@0	2382	** outB: Move the output of the selectB coroutine into the output
sl@0	2383	** of the compound query. (Only generated for UNION and
sl@0	2384	** UNION ALL. EXCEPT and INSERTSECT never output a row that
sl@0	2385	** appears only in B.)
sl@0	2386	**
sl@0	2387	** AltB: Called when there is data from both coroutines and A<B.
sl@0	2388	**
sl@0	2389	** AeqB: Called when there is data from both coroutines and A==B.
sl@0	2390	**
sl@0	2391	** AgtB: Called when there is data from both coroutines and A>B.
sl@0	2392	**
sl@0	2393	** EofA: Called when data is exhausted from selectA.
sl@0	2394	**
sl@0	2395	** EofB: Called when data is exhausted from selectB.
sl@0	2396	**
sl@0	2397	** The implementation of the latter five subroutines depend on which
sl@0	2398	** <operator> is used:
sl@0	2399	**
sl@0	2400	**
sl@0	2401	** UNION ALL UNION EXCEPT INTERSECT
sl@0	2402	** ------------- ----------------- -------------- -----------------
sl@0	2403	** AltB: outA, nextA outA, nextA outA, nextA nextA
sl@0	2404	**
sl@0	2405	** AeqB: outA, nextA nextA nextA outA, nextA
sl@0	2406	**
sl@0	2407	** AgtB: outB, nextB outB, nextB nextB nextB
sl@0	2408	**
sl@0	2409	** EofA: outB, nextB outB, nextB halt halt
sl@0	2410	**
sl@0	2411	** EofB: outA, nextA outA, nextA outA, nextA halt
sl@0	2412	**
sl@0	2413	** In the AltB, AeqB, and AgtB subroutines, an EOF on A following nextA
sl@0	2414	** causes an immediate jump to EofA and an EOF on B following nextB causes
sl@0	2415	** an immediate jump to EofB. Within EofA and EofB, and EOF on entry or
sl@0	2416	** following nextX causes a jump to the end of the select processing.
sl@0	2417	**
sl@0	2418	** Duplicate removal in the UNION, EXCEPT, and INTERSECT cases is handled
sl@0	2419	** within the output subroutine. The regPrev register set holds the previously
sl@0	2420	** output value. A comparison is made against this value and the output
sl@0	2421	** is skipped if the next results would be the same as the previous.
sl@0	2422	**
sl@0	2423	** The implementation plan is to implement the two coroutines and seven
sl@0	2424	** subroutines first, then put the control logic at the bottom. Like this:
sl@0	2425	**
sl@0	2426	** goto Init
sl@0	2427	** coA: coroutine for left query (A)
sl@0	2428	** coB: coroutine for right query (B)
sl@0	2429	** outA: output one row of A
sl@0	2430	** outB: output one row of B (UNION and UNION ALL only)
sl@0	2431	** EofA: ...
sl@0	2432	** EofB: ...
sl@0	2433	** AltB: ...
sl@0	2434	** AeqB: ...
sl@0	2435	** AgtB: ...
sl@0	2436	** Init: initialize coroutine registers
sl@0	2437	** yield coA
sl@0	2438	** if eof(A) goto EofA
sl@0	2439	** yield coB
sl@0	2440	** if eof(B) goto EofB
sl@0	2441	** Cmpr: Compare A, B
sl@0	2442	** Jump AltB, AeqB, AgtB
sl@0	2443	** End: ...
sl@0	2444	**
sl@0	2445	** We call AltB, AeqB, AgtB, EofA, and EofB "subroutines" but they are not
sl@0	2446	** actually called using Gosub and they do not Return. EofA and EofB loop
sl@0	2447	** until all data is exhausted then jump to the "end" labe. AltB, AeqB,
sl@0	2448	** and AgtB jump to either L2 or to one of EofA or EofB.
sl@0	2449	*/
sl@0	2450	#ifndef SQLITE_OMIT_COMPOUND_SELECT
sl@0	2451	static int multiSelectOrderBy(
sl@0	2452	Parse pParse, / Parsing context */
sl@0	2453	Select p, / The right-most of SELECTs to be coded */
sl@0	2454	SelectDest pDest / What to do with query results */
sl@0	2455	){
sl@0	2456	int i, j; /* Loop counters */
sl@0	2457	Select pPrior; / Another SELECT immediately to our left */
sl@0	2458	Vdbe v; / Generate code to this VDBE */
sl@0	2459	SelectDest destA; /* Destination for coroutine A */
sl@0	2460	SelectDest destB; /* Destination for coroutine B */
sl@0	2461	int regAddrA; /* Address register for select-A coroutine */
sl@0	2462	int regEofA; /* Flag to indicate when select-A is complete */
sl@0	2463	int regAddrB; /* Address register for select-B coroutine */
sl@0	2464	int regEofB; /* Flag to indicate when select-B is complete */
sl@0	2465	int addrSelectA; /* Address of the select-A coroutine */
sl@0	2466	int addrSelectB; /* Address of the select-B coroutine */
sl@0	2467	int regOutA; /* Address register for the output-A subroutine */
sl@0	2468	int regOutB; /* Address register for the output-B subroutine */
sl@0	2469	int addrOutA; /* Address of the output-A subroutine */
sl@0	2470	int addrOutB = 0; /* Address of the output-B subroutine */
sl@0	2471	int addrEofA; /* Address of the select-A-exhausted subroutine */
sl@0	2472	int addrEofB; /* Address of the select-B-exhausted subroutine */
sl@0	2473	int addrAltB; /* Address of the A<B subroutine */
sl@0	2474	int addrAeqB; /* Address of the A==B subroutine */
sl@0	2475	int addrAgtB; /* Address of the A>B subroutine */
sl@0	2476	int regLimitA; /* Limit register for select-A */
sl@0	2477	int regLimitB; /* Limit register for select-A */
sl@0	2478	int regPrev; /* A range of registers to hold previous output */
sl@0	2479	int savedLimit; /* Saved value of p->iLimit */
sl@0	2480	int savedOffset; /* Saved value of p->iOffset */
sl@0	2481	int labelCmpr; /* Label for the start of the merge algorithm */
sl@0	2482	int labelEnd; /* Label for the end of the overall SELECT stmt */
sl@0	2483	int j1; /* Jump instructions that get retargetted */
sl@0	2484	int op; /* One of TK_ALL, TK_UNION, TK_EXCEPT, TK_INTERSECT */
sl@0	2485	KeyInfo pKeyDup = 0; / Comparison information for duplicate removal */
sl@0	2486	KeyInfo pKeyMerge; / Comparison information for merging rows */
sl@0	2487	sqlite3 db; / Database connection */
sl@0	2488	ExprList pOrderBy; / The ORDER BY clause */
sl@0	2489	int nOrderBy; /* Number of terms in the ORDER BY clause */
sl@0	2490	int aPermute; / Mapping from ORDER BY terms to result set columns */
sl@0	2491	u8 NotUsed; /* Dummy variables */
sl@0	2492
sl@0	2493	assert( p->pOrderBy!=0 );
sl@0	2494	db = pParse->db;
sl@0	2495	v = pParse->pVdbe;
sl@0	2496	if( v==0 ) return SQLITE_NOMEM;
sl@0	2497	labelEnd = sqlite3VdbeMakeLabel(v);
sl@0	2498	labelCmpr = sqlite3VdbeMakeLabel(v);
sl@0	2499
sl@0	2500
sl@0	2501	/* Patch up the ORDER BY clause
sl@0	2502	*/
sl@0	2503	op = p->op;
sl@0	2504	pPrior = p->pPrior;
sl@0	2505	assert( pPrior->pOrderBy==0 );
sl@0	2506	pOrderBy = p->pOrderBy;
sl@0	2507	assert( pOrderBy );
sl@0	2508	if( processCompoundOrderBy(pParse, p) ){
sl@0	2509	return SQLITE_ERROR;
sl@0	2510	}
sl@0	2511	nOrderBy = pOrderBy->nExpr;
sl@0	2512
sl@0	2513	/* For operators other than UNION ALL we have to make sure that
sl@0	2514	** the ORDER BY clause covers every term of the result set. Add
sl@0	2515	** terms to the ORDER BY clause as necessary.
sl@0	2516	*/
sl@0	2517	if( op!=TK_ALL ){
sl@0	2518	for(i=1; db->mallocFailed==0 && i<=p->pEList->nExpr; i++){
sl@0	2519	for(j=0; j<nOrderBy; j++){
sl@0	2520	Expr *pTerm = pOrderBy->a[j].pExpr;
sl@0	2521	assert( pTerm->op==TK_INTEGER );
sl@0	2522	assert( (pTerm->flags & EP_IntValue)!=0 );
sl@0	2523	if( pTerm->iTable==i ) break;
sl@0	2524	}
sl@0	2525	if( j==nOrderBy ){
sl@0	2526	Expr *pNew = sqlite3PExpr(pParse, TK_INTEGER, 0, 0, 0);
sl@0	2527	if( pNew==0 ) return SQLITE_NOMEM;
sl@0	2528	pNew->flags \|= EP_IntValue;
sl@0	2529	pNew->iTable = i;
sl@0	2530	pOrderBy = sqlite3ExprListAppend(pParse, pOrderBy, pNew, 0);
sl@0	2531	nOrderBy++;
sl@0	2532	}
sl@0	2533	}
sl@0	2534	}
sl@0	2535
sl@0	2536	/* Compute the comparison permutation and keyinfo that is used with
sl@0	2537	** the permutation in order to comparisons to determine if the next
sl@0	2538	** row of results comes from selectA or selectB. Also add explicit
sl@0	2539	** collations to the ORDER BY clause terms so that when the subqueries
sl@0	2540	** to the right and the left are evaluated, they use the correct
sl@0	2541	** collation.
sl@0	2542	*/
sl@0	2543	aPermute = sqlite3DbMallocRaw(db, sizeof(int)*nOrderBy);
sl@0	2544	if( aPermute ){
sl@0	2545	for(i=0; i<nOrderBy; i++){
sl@0	2546	Expr *pTerm = pOrderBy->a[i].pExpr;
sl@0	2547	assert( pTerm->op==TK_INTEGER );
sl@0	2548	assert( (pTerm->flags & EP_IntValue)!=0 );
sl@0	2549	aPermute[i] = pTerm->iTable-1;
sl@0	2550	assert( aPermute[i]>=0 && aPermute[i]<p->pEList->nExpr );
sl@0	2551	}
sl@0	2552	pKeyMerge =
sl@0	2553	sqlite3DbMallocRaw(db, sizeof(pKeyMerge)+nOrderBy(sizeof(CollSeq*)+1));
sl@0	2554	if( pKeyMerge ){
sl@0	2555	pKeyMerge->aSortOrder = (u8*)&pKeyMerge->aColl[nOrderBy];
sl@0	2556	pKeyMerge->nField = nOrderBy;
sl@0	2557	pKeyMerge->enc = ENC(db);
sl@0	2558	for(i=0; i<nOrderBy; i++){
sl@0	2559	CollSeq *pColl;
sl@0	2560	Expr *pTerm = pOrderBy->a[i].pExpr;
sl@0	2561	if( pTerm->flags & EP_ExpCollate ){
sl@0	2562	pColl = pTerm->pColl;
sl@0	2563	}else{
sl@0	2564	pColl = multiSelectCollSeq(pParse, p, aPermute[i]);
sl@0	2565	pTerm->flags \|= EP_ExpCollate;
sl@0	2566	pTerm->pColl = pColl;
sl@0	2567	}
sl@0	2568	pKeyMerge->aColl[i] = pColl;
sl@0	2569	pKeyMerge->aSortOrder[i] = pOrderBy->a[i].sortOrder;
sl@0	2570	}
sl@0	2571	}
sl@0	2572	}else{
sl@0	2573	pKeyMerge = 0;
sl@0	2574	}
sl@0	2575
sl@0	2576	/* Reattach the ORDER BY clause to the query.
sl@0	2577	*/
sl@0	2578	p->pOrderBy = pOrderBy;
sl@0	2579	pPrior->pOrderBy = sqlite3ExprListDup(pParse->db, pOrderBy);
sl@0	2580
sl@0	2581	/* Allocate a range of temporary registers and the KeyInfo needed
sl@0	2582	** for the logic that removes duplicate result rows when the
sl@0	2583	** operator is UNION, EXCEPT, or INTERSECT (but not UNION ALL).
sl@0	2584	*/
sl@0	2585	if( op==TK_ALL ){
sl@0	2586	regPrev = 0;
sl@0	2587	}else{
sl@0	2588	int nExpr = p->pEList->nExpr;
sl@0	2589	assert( nOrderBy>=nExpr );
sl@0	2590	regPrev = sqlite3GetTempRange(pParse, nExpr+1);
sl@0	2591	sqlite3VdbeAddOp2(v, OP_Integer, 0, regPrev);
sl@0	2592	pKeyDup = sqlite3DbMallocZero(db,
sl@0	2593	sizeof(pKeyDup) + nExpr(sizeof(CollSeq*)+1) );
sl@0	2594	if( pKeyDup ){
sl@0	2595	pKeyDup->aSortOrder = (u8*)&pKeyDup->aColl[nExpr];
sl@0	2596	pKeyDup->nField = nExpr;
sl@0	2597	pKeyDup->enc = ENC(db);
sl@0	2598	for(i=0; i<nExpr; i++){
sl@0	2599	pKeyDup->aColl[i] = multiSelectCollSeq(pParse, p, i);
sl@0	2600	pKeyDup->aSortOrder[i] = 0;
sl@0	2601	}
sl@0	2602	}
sl@0	2603	}
sl@0	2604
sl@0	2605	/* Separate the left and the right query from one another
sl@0	2606	*/
sl@0	2607	p->pPrior = 0;
sl@0	2608	pPrior->pRightmost = 0;
sl@0	2609	processOrderGroupBy(pParse, p, p->pOrderBy, 1, &NotUsed);
sl@0	2610	if( pPrior->pPrior==0 ){
sl@0	2611	processOrderGroupBy(pParse, pPrior, pPrior->pOrderBy, 1, &NotUsed);
sl@0	2612	}
sl@0	2613
sl@0	2614	/* Compute the limit registers */
sl@0	2615	computeLimitRegisters(pParse, p, labelEnd);
sl@0	2616	if( p->iLimit && op==TK_ALL ){
sl@0	2617	regLimitA = ++pParse->nMem;
sl@0	2618	regLimitB = ++pParse->nMem;
sl@0	2619	sqlite3VdbeAddOp2(v, OP_Copy, p->iOffset ? p->iOffset+1 : p->iLimit,
sl@0	2620	regLimitA);
sl@0	2621	sqlite3VdbeAddOp2(v, OP_Copy, regLimitA, regLimitB);
sl@0	2622	}else{
sl@0	2623	regLimitA = regLimitB = 0;
sl@0	2624	}
sl@0	2625	sqlite3ExprDelete(db, p->pLimit);
sl@0	2626	p->pLimit = 0;
sl@0	2627	sqlite3ExprDelete(db, p->pOffset);
sl@0	2628	p->pOffset = 0;
sl@0	2629
sl@0	2630	regAddrA = ++pParse->nMem;
sl@0	2631	regEofA = ++pParse->nMem;
sl@0	2632	regAddrB = ++pParse->nMem;
sl@0	2633	regEofB = ++pParse->nMem;
sl@0	2634	regOutA = ++pParse->nMem;
sl@0	2635	regOutB = ++pParse->nMem;
sl@0	2636	sqlite3SelectDestInit(&destA, SRT_Coroutine, regAddrA);
sl@0	2637	sqlite3SelectDestInit(&destB, SRT_Coroutine, regAddrB);
sl@0	2638
sl@0	2639	/* Jump past the various subroutines and coroutines to the main
sl@0	2640	** merge loop
sl@0	2641	*/
sl@0	2642	j1 = sqlite3VdbeAddOp0(v, OP_Goto);
sl@0	2643	addrSelectA = sqlite3VdbeCurrentAddr(v);
sl@0	2644
sl@0	2645
sl@0	2646	/* Generate a coroutine to evaluate the SELECT statement to the
sl@0	2647	** left of the compound operator - the "A" select.
sl@0	2648	*/
sl@0	2649	VdbeNoopComment((v, "Begin coroutine for left SELECT"));
sl@0	2650	pPrior->iLimit = regLimitA;
sl@0	2651	sqlite3Select(pParse, pPrior, &destA, 0, 0, 0);
sl@0	2652	sqlite3VdbeAddOp2(v, OP_Integer, 1, regEofA);
sl@0	2653	sqlite3VdbeAddOp1(v, OP_Yield, regAddrA);
sl@0	2654	VdbeNoopComment((v, "End coroutine for left SELECT"));
sl@0	2655
sl@0	2656	/* Generate a coroutine to evaluate the SELECT statement on
sl@0	2657	** the right - the "B" select
sl@0	2658	*/
sl@0	2659	addrSelectB = sqlite3VdbeCurrentAddr(v);
sl@0	2660	VdbeNoopComment((v, "Begin coroutine for right SELECT"));
sl@0	2661	savedLimit = p->iLimit;
sl@0	2662	savedOffset = p->iOffset;
sl@0	2663	p->iLimit = regLimitB;
sl@0	2664	p->iOffset = 0;
sl@0	2665	sqlite3Select(pParse, p, &destB, 0, 0, 0);
sl@0	2666	p->iLimit = savedLimit;
sl@0	2667	p->iOffset = savedOffset;
sl@0	2668	sqlite3VdbeAddOp2(v, OP_Integer, 1, regEofB);
sl@0	2669	sqlite3VdbeAddOp1(v, OP_Yield, regAddrB);
sl@0	2670	VdbeNoopComment((v, "End coroutine for right SELECT"));
sl@0	2671
sl@0	2672	/* Generate a subroutine that outputs the current row of the A
sl@0	2673	** select as the next output row of the compound select.
sl@0	2674	*/
sl@0	2675	VdbeNoopComment((v, "Output routine for A"));
sl@0	2676	addrOutA = generateOutputSubroutine(pParse,
sl@0	2677	p, &destA, pDest, regOutA,
sl@0	2678	regPrev, pKeyDup, P4_KEYINFO_HANDOFF, labelEnd);
sl@0	2679
sl@0	2680	/* Generate a subroutine that outputs the current row of the B
sl@0	2681	** select as the next output row of the compound select.
sl@0	2682	*/
sl@0	2683	if( op==TK_ALL \|\| op==TK_UNION ){
sl@0	2684	VdbeNoopComment((v, "Output routine for B"));
sl@0	2685	addrOutB = generateOutputSubroutine(pParse,
sl@0	2686	p, &destB, pDest, regOutB,
sl@0	2687	regPrev, pKeyDup, P4_KEYINFO_STATIC, labelEnd);
sl@0	2688	}
sl@0	2689
sl@0	2690	/* Generate a subroutine to run when the results from select A
sl@0	2691	** are exhausted and only data in select B remains.
sl@0	2692	*/
sl@0	2693	VdbeNoopComment((v, "eof-A subroutine"));
sl@0	2694	if( op==TK_EXCEPT \|\| op==TK_INTERSECT ){
sl@0	2695	addrEofA = sqlite3VdbeAddOp2(v, OP_Goto, 0, labelEnd);
sl@0	2696	}else{
sl@0	2697	addrEofA = sqlite3VdbeAddOp2(v, OP_If, regEofB, labelEnd);
sl@0	2698	sqlite3VdbeAddOp2(v, OP_Gosub, regOutB, addrOutB);
sl@0	2699	sqlite3VdbeAddOp1(v, OP_Yield, regAddrB);
sl@0	2700	sqlite3VdbeAddOp2(v, OP_Goto, 0, addrEofA);
sl@0	2701	}
sl@0	2702
sl@0	2703	/* Generate a subroutine to run when the results from select B
sl@0	2704	** are exhausted and only data in select A remains.
sl@0	2705	*/
sl@0	2706	if( op==TK_INTERSECT ){
sl@0	2707	addrEofB = addrEofA;
sl@0	2708	}else{
sl@0	2709	VdbeNoopComment((v, "eof-B subroutine"));
sl@0	2710	addrEofB = sqlite3VdbeAddOp2(v, OP_If, regEofA, labelEnd);
sl@0	2711	sqlite3VdbeAddOp2(v, OP_Gosub, regOutA, addrOutA);
sl@0	2712	sqlite3VdbeAddOp1(v, OP_Yield, regAddrA);
sl@0	2713	sqlite3VdbeAddOp2(v, OP_Goto, 0, addrEofB);
sl@0	2714	}
sl@0	2715
sl@0	2716	/* Generate code to handle the case of A<B
sl@0	2717	*/
sl@0	2718	VdbeNoopComment((v, "A-lt-B subroutine"));
sl@0	2719	addrAltB = sqlite3VdbeAddOp2(v, OP_Gosub, regOutA, addrOutA);
sl@0	2720	sqlite3VdbeAddOp1(v, OP_Yield, regAddrA);
sl@0	2721	sqlite3VdbeAddOp2(v, OP_If, regEofA, addrEofA);
sl@0	2722	sqlite3VdbeAddOp2(v, OP_Goto, 0, labelCmpr);
sl@0	2723
sl@0	2724	/* Generate code to handle the case of A==B
sl@0	2725	*/
sl@0	2726	if( op==TK_ALL ){
sl@0	2727	addrAeqB = addrAltB;
sl@0	2728	}else if( op==TK_INTERSECT ){
sl@0	2729	addrAeqB = addrAltB;
sl@0	2730	addrAltB++;
sl@0	2731	}else{
sl@0	2732	VdbeNoopComment((v, "A-eq-B subroutine"));
sl@0	2733	addrAeqB =
sl@0	2734	sqlite3VdbeAddOp1(v, OP_Yield, regAddrA);
sl@0	2735	sqlite3VdbeAddOp2(v, OP_If, regEofA, addrEofA);
sl@0	2736	sqlite3VdbeAddOp2(v, OP_Goto, 0, labelCmpr);
sl@0	2737	}
sl@0	2738
sl@0	2739	/* Generate code to handle the case of A>B
sl@0	2740	*/
sl@0	2741	VdbeNoopComment((v, "A-gt-B subroutine"));
sl@0	2742	addrAgtB = sqlite3VdbeCurrentAddr(v);
sl@0	2743	if( op==TK_ALL \|\| op==TK_UNION ){
sl@0	2744	sqlite3VdbeAddOp2(v, OP_Gosub, regOutB, addrOutB);
sl@0	2745	}
sl@0	2746	sqlite3VdbeAddOp1(v, OP_Yield, regAddrB);
sl@0	2747	sqlite3VdbeAddOp2(v, OP_If, regEofB, addrEofB);
sl@0	2748	sqlite3VdbeAddOp2(v, OP_Goto, 0, labelCmpr);
sl@0	2749
sl@0	2750	/* This code runs once to initialize everything.
sl@0	2751	*/
sl@0	2752	sqlite3VdbeJumpHere(v, j1);
sl@0	2753	sqlite3VdbeAddOp2(v, OP_Integer, 0, regEofA);
sl@0	2754	sqlite3VdbeAddOp2(v, OP_Integer, 0, regEofB);
sl@0	2755	sqlite3VdbeAddOp2(v, OP_Gosub, regAddrA, addrSelectA);
sl@0	2756	sqlite3VdbeAddOp2(v, OP_Gosub, regAddrB, addrSelectB);
sl@0	2757	sqlite3VdbeAddOp2(v, OP_If, regEofA, addrEofA);
sl@0	2758	sqlite3VdbeAddOp2(v, OP_If, regEofB, addrEofB);
sl@0	2759
sl@0	2760	/* Implement the main merge loop
sl@0	2761	*/
sl@0	2762	sqlite3VdbeResolveLabel(v, labelCmpr);
sl@0	2763	sqlite3VdbeAddOp4(v, OP_Permutation, 0, 0, 0, (char*)aPermute, P4_INTARRAY);
sl@0	2764	sqlite3VdbeAddOp4(v, OP_Compare, destA.iMem, destB.iMem, nOrderBy,
sl@0	2765	(char*)pKeyMerge, P4_KEYINFO_HANDOFF);
sl@0	2766	sqlite3VdbeAddOp3(v, OP_Jump, addrAltB, addrAeqB, addrAgtB);
sl@0	2767
sl@0	2768	/* Release temporary registers
sl@0	2769	*/
sl@0	2770	if( regPrev ){
sl@0	2771	sqlite3ReleaseTempRange(pParse, regPrev, nOrderBy+1);
sl@0	2772	}
sl@0	2773
sl@0	2774	/* Jump to the this point in order to terminate the query.
sl@0	2775	*/
sl@0	2776	sqlite3VdbeResolveLabel(v, labelEnd);
sl@0	2777
sl@0	2778	/* Set the number of output columns
sl@0	2779	*/
sl@0	2780	if( pDest->eDest==SRT_Callback ){
sl@0	2781	Select *pFirst = pPrior;
sl@0	2782	while( pFirst->pPrior ) pFirst = pFirst->pPrior;
sl@0	2783	generateColumnNames(pParse, 0, pFirst->pEList);
sl@0	2784	}
sl@0	2785
sl@0	2786	/* Reassembly the compound query so that it will be freed correctly
sl@0	2787	** by the calling function */
sl@0	2788	if( p->pPrior ){
sl@0	2789	sqlite3SelectDelete(db, p->pPrior);
sl@0	2790	}
sl@0	2791	p->pPrior = pPrior;
sl@0	2792
sl@0	2793	/*** TBD: Insert subroutine calls to close cursors on incomplete
sl@0	2794	** subqueries **/
sl@0	2795	return SQLITE_OK;
sl@0	2796	}
sl@0	2797	#endif
sl@0	2798
sl@0	2799	#if !defined(SQLITE_OMIT_SUBQUERY) \|\| !defined(SQLITE_OMIT_VIEW)
sl@0	2800	/* Forward Declarations */
sl@0	2801	static void substExprList(sqlite3, ExprList, int, ExprList*);
sl@0	2802	static void substSelect(sqlite3, Select , int, ExprList *);
sl@0	2803
sl@0	2804	/*
sl@0	2805	** Scan through the expression pExpr. Replace every reference to
sl@0	2806	** a column in table number iTable with a copy of the iColumn-th
sl@0	2807	** entry in pEList. (But leave references to the ROWID column
sl@0	2808	** unchanged.)
sl@0	2809	**
sl@0	2810	** This routine is part of the flattening procedure. A subquery
sl@0	2811	** whose result set is defined by pEList appears as entry in the
sl@0	2812	** FROM clause of a SELECT such that the VDBE cursor assigned to that
sl@0	2813	** FORM clause entry is iTable. This routine make the necessary
sl@0	2814	** changes to pExpr so that it refers directly to the source table
sl@0	2815	** of the subquery rather the result set of the subquery.
sl@0	2816	*/
sl@0	2817	static void substExpr(
sl@0	2818	sqlite3 db, / Report malloc errors to this connection */
sl@0	2819	Expr pExpr, / Expr in which substitution occurs */
sl@0	2820	int iTable, /* Table to be substituted */
sl@0	2821	ExprList pEList / Substitute expressions */
sl@0	2822	){
sl@0	2823	if( pExpr==0 ) return;
sl@0	2824	if( pExpr->op==TK_COLUMN && pExpr->iTable==iTable ){
sl@0	2825	if( pExpr->iColumn<0 ){
sl@0	2826	pExpr->op = TK_NULL;
sl@0	2827	}else{
sl@0	2828	Expr *pNew;
sl@0	2829	assert( pEList!=0 && pExpr->iColumn<pEList->nExpr );
sl@0	2830	assert( pExpr->pLeft==0 && pExpr->pRight==0 && pExpr->pList==0 );
sl@0	2831	pNew = pEList->a[pExpr->iColumn].pExpr;
sl@0	2832	assert( pNew!=0 );
sl@0	2833	pExpr->op = pNew->op;
sl@0	2834	assert( pExpr->pLeft==0 );
sl@0	2835	pExpr->pLeft = sqlite3ExprDup(db, pNew->pLeft);
sl@0	2836	assert( pExpr->pRight==0 );
sl@0	2837	pExpr->pRight = sqlite3ExprDup(db, pNew->pRight);
sl@0	2838	assert( pExpr->pList==0 );
sl@0	2839	pExpr->pList = sqlite3ExprListDup(db, pNew->pList);
sl@0	2840	pExpr->iTable = pNew->iTable;
sl@0	2841	pExpr->pTab = pNew->pTab;
sl@0	2842	pExpr->iColumn = pNew->iColumn;
sl@0	2843	pExpr->iAgg = pNew->iAgg;
sl@0	2844	sqlite3TokenCopy(db, &pExpr->token, &pNew->token);
sl@0	2845	sqlite3TokenCopy(db, &pExpr->span, &pNew->span);
sl@0	2846	pExpr->pSelect = sqlite3SelectDup(db, pNew->pSelect);
sl@0	2847	pExpr->flags = pNew->flags;
sl@0	2848	}
sl@0	2849	}else{
sl@0	2850	substExpr(db, pExpr->pLeft, iTable, pEList);
sl@0	2851	substExpr(db, pExpr->pRight, iTable, pEList);
sl@0	2852	substSelect(db, pExpr->pSelect, iTable, pEList);
sl@0	2853	substExprList(db, pExpr->pList, iTable, pEList);
sl@0	2854	}
sl@0	2855	}
sl@0	2856	static void substExprList(
sl@0	2857	sqlite3 db, / Report malloc errors here */
sl@0	2858	ExprList pList, / List to scan and in which to make substitutes */
sl@0	2859	int iTable, /* Table to be substituted */
sl@0	2860	ExprList pEList / Substitute values */
sl@0	2861	){
sl@0	2862	int i;
sl@0	2863	if( pList==0 ) return;
sl@0	2864	for(i=0; i<pList->nExpr; i++){
sl@0	2865	substExpr(db, pList->a[i].pExpr, iTable, pEList);
sl@0	2866	}
sl@0	2867	}
sl@0	2868	static void substSelect(
sl@0	2869	sqlite3 db, / Report malloc errors here */
sl@0	2870	Select p, / SELECT statement in which to make substitutions */
sl@0	2871	int iTable, /* Table to be replaced */
sl@0	2872	ExprList pEList / Substitute values */
sl@0	2873	){
sl@0	2874	if( !p ) return;
sl@0	2875	substExprList(db, p->pEList, iTable, pEList);
sl@0	2876	substExprList(db, p->pGroupBy, iTable, pEList);
sl@0	2877	substExprList(db, p->pOrderBy, iTable, pEList);
sl@0	2878	substExpr(db, p->pHaving, iTable, pEList);
sl@0	2879	substExpr(db, p->pWhere, iTable, pEList);
sl@0	2880	substSelect(db, p->pPrior, iTable, pEList);
sl@0	2881	}
sl@0	2882	#endif /* !defined(SQLITE_OMIT_SUBQUERY) \|\| !defined(SQLITE_OMIT_VIEW) */
sl@0	2883
sl@0	2884	#if !defined(SQLITE_OMIT_SUBQUERY) \|\| !defined(SQLITE_OMIT_VIEW)
sl@0	2885	/*
sl@0	2886	** This routine attempts to flatten subqueries in order to speed
sl@0	2887	** execution. It returns 1 if it makes changes and 0 if no flattening
sl@0	2888	** occurs.
sl@0	2889	**
sl@0	2890	** To understand the concept of flattening, consider the following
sl@0	2891	** query:
sl@0	2892	**
sl@0	2893	** SELECT a FROM (SELECT x+y AS a FROM t1 WHERE z<100) WHERE a>5
sl@0	2894	**
sl@0	2895	** The default way of implementing this query is to execute the
sl@0	2896	** subquery first and store the results in a temporary table, then
sl@0	2897	** run the outer query on that temporary table. This requires two
sl@0	2898	** passes over the data. Furthermore, because the temporary table
sl@0	2899	** has no indices, the WHERE clause on the outer query cannot be
sl@0	2900	** optimized.
sl@0	2901	**
sl@0	2902	** This routine attempts to rewrite queries such as the above into
sl@0	2903	** a single flat select, like this:
sl@0	2904	**
sl@0	2905	** SELECT x+y AS a FROM t1 WHERE z<100 AND a>5
sl@0	2906	**
sl@0	2907	** The code generated for this simpification gives the same result
sl@0	2908	** but only has to scan the data once. And because indices might
sl@0	2909	** exist on the table t1, a complete scan of the data might be
sl@0	2910	** avoided.
sl@0	2911	**
sl@0	2912	** Flattening is only attempted if all of the following are true:
sl@0	2913	**
sl@0	2914	** (1) The subquery and the outer query do not both use aggregates.
sl@0	2915	**
sl@0	2916	** (2) The subquery is not an aggregate or the outer query is not a join.
sl@0	2917	**
sl@0	2918	** (3) The subquery is not the right operand of a left outer join, or
sl@0	2919	** the subquery is not itself a join. (Ticket #306)
sl@0	2920	**
sl@0	2921	** (4) The subquery is not DISTINCT or the outer query is not a join.
sl@0	2922	**
sl@0	2923	** (5) The subquery is not DISTINCT or the outer query does not use
sl@0	2924	** aggregates.
sl@0	2925	**
sl@0	2926	** (6) The subquery does not use aggregates or the outer query is not
sl@0	2927	** DISTINCT.
sl@0	2928	**
sl@0	2929	** (7) The subquery has a FROM clause.
sl@0	2930	**
sl@0	2931	** (8) The subquery does not use LIMIT or the outer query is not a join.
sl@0	2932	**
sl@0	2933	** (9) The subquery does not use LIMIT or the outer query does not use
sl@0	2934	** aggregates.
sl@0	2935	**
sl@0	2936	** (10) The subquery does not use aggregates or the outer query does not
sl@0	2937	** use LIMIT.
sl@0	2938	**
sl@0	2939	** (11) The subquery and the outer query do not both have ORDER BY clauses.
sl@0	2940	**
sl@0	2941	** (12) The subquery is not the right term of a LEFT OUTER JOIN or the
sl@0	2942	** subquery has no WHERE clause. (added by ticket #350)
sl@0	2943	**
sl@0	2944	** (13) The subquery and outer query do not both use LIMIT
sl@0	2945	**
sl@0	2946	** (14) The subquery does not use OFFSET
sl@0	2947	**
sl@0	2948	** (15) The outer query is not part of a compound select or the
sl@0	2949	** subquery does not have both an ORDER BY and a LIMIT clause.
sl@0	2950	** (See ticket #2339)
sl@0	2951	**
sl@0	2952	** (16) The outer query is not an aggregate or the subquery does
sl@0	2953	** not contain ORDER BY. (Ticket #2942) This used to not matter
sl@0	2954	** until we introduced the group_concat() function.
sl@0	2955	**
sl@0	2956	** (17) The sub-query is not a compound select, or it is a UNION ALL
sl@0	2957	** compound clause made up entirely of non-aggregate queries, and
sl@0	2958	** the parent query:
sl@0	2959	**
sl@0	2960	** * is not itself part of a compound select,
sl@0	2961	** * is not an aggregate or DISTINCT query, and
sl@0	2962	** * has no other tables or sub-selects in the FROM clause.
sl@0	2963	**
sl@0	2964	** The parent and sub-query may contain WHERE clauses. Subject to
sl@0	2965	** rules (11), (13) and (14), they may also contain ORDER BY,
sl@0	2966	** LIMIT and OFFSET clauses.
sl@0	2967	**
sl@0	2968	** (18) If the sub-query is a compound select, then all terms of the
sl@0	2969	** ORDER by clause of the parent must be simple references to
sl@0	2970	** columns of the sub-query.
sl@0	2971	**
sl@0	2972	** In this routine, the "p" parameter is a pointer to the outer query.
sl@0	2973	** The subquery is p->pSrc->a[iFrom]. isAgg is true if the outer query
sl@0	2974	** uses aggregates and subqueryIsAgg is true if the subquery uses aggregates.
sl@0	2975	**
sl@0	2976	** If flattening is not attempted, this routine is a no-op and returns 0.
sl@0	2977	** If flattening is attempted this routine returns 1.
sl@0	2978	**
sl@0	2979	** All of the expression analysis must occur on both the outer query and
sl@0	2980	** the subquery before this routine runs.
sl@0	2981	*/
sl@0	2982	static int flattenSubquery(
sl@0	2983	Parse pParse, / Parsing context */
sl@0	2984	Select p, / The parent or outer SELECT statement */
sl@0	2985	int iFrom, /* Index in p->pSrc->a[] of the inner subquery */
sl@0	2986	int isAgg, /* True if outer SELECT uses aggregate functions */
sl@0	2987	int subqueryIsAgg /* True if the subquery uses aggregate functions */
sl@0	2988	){
sl@0	2989	const char *zSavedAuthContext = pParse->zAuthContext;
sl@0	2990	Select *pParent;
sl@0	2991	Select pSub; / The inner query or "subquery" */
sl@0	2992	Select pSub1; / Pointer to the rightmost select in sub-query */
sl@0	2993	SrcList pSrc; / The FROM clause of the outer query */
sl@0	2994	SrcList pSubSrc; / The FROM clause of the subquery */
sl@0	2995	ExprList pList; / The result set of the outer query */
sl@0	2996	int iParent; /* VDBE cursor number of the pSub result set temp table */
sl@0	2997	int i; /* Loop counter */
sl@0	2998	Expr pWhere; / The WHERE clause */
sl@0	2999	struct SrcList_item pSubitem; / The subquery */
sl@0	3000	sqlite3 *db = pParse->db;
sl@0	3001
sl@0	3002	/* Check to see if flattening is permitted. Return 0 if not.
sl@0	3003	*/
sl@0	3004	if( p==0 ) return 0;
sl@0	3005	pSrc = p->pSrc;
sl@0	3006	assert( pSrc && iFrom>=0 && iFrom<pSrc->nSrc );
sl@0	3007	pSubitem = &pSrc->a[iFrom];
sl@0	3008	iParent = pSubitem->iCursor;
sl@0	3009	pSub = pSubitem->pSelect;
sl@0	3010	assert( pSub!=0 );
sl@0	3011	if( isAgg && subqueryIsAgg ) return 0; /* Restriction (1) */
sl@0	3012	if( subqueryIsAgg && pSrc->nSrc>1 ) return 0; /* Restriction (2) */
sl@0	3013	pSubSrc = pSub->pSrc;
sl@0	3014	assert( pSubSrc );
sl@0	3015	/* Prior to version 3.1.2, when LIMIT and OFFSET had to be simple constants,
sl@0	3016	** not arbitrary expresssions, we allowed some combining of LIMIT and OFFSET
sl@0	3017	** because they could be computed at compile-time. But when LIMIT and OFFSET
sl@0	3018	** became arbitrary expressions, we were forced to add restrictions (13)
sl@0	3019	** and (14). */
sl@0	3020	if( pSub->pLimit && p->pLimit ) return 0; /* Restriction (13) */
sl@0	3021	if( pSub->pOffset ) return 0; /* Restriction (14) */
sl@0	3022	if( p->pRightmost && pSub->pLimit && pSub->pOrderBy ){
sl@0	3023	return 0; /* Restriction (15) */
sl@0	3024	}
sl@0	3025	if( pSubSrc->nSrc==0 ) return 0; /* Restriction (7) */
sl@0	3026	if( (pSub->isDistinct \|\| pSub->pLimit)
sl@0	3027	&& (pSrc->nSrc>1 \|\| isAgg) ){ /* Restrictions (4)(5)(8)(9) */
sl@0	3028	return 0;
sl@0	3029	}
sl@0	3030	if( p->isDistinct && subqueryIsAgg ) return 0; /* Restriction (6) */
sl@0	3031	if( (p->disallowOrderBy \|\| p->pOrderBy) && pSub->pOrderBy ){
sl@0	3032	return 0; /* Restriction (11) */
sl@0	3033	}
sl@0	3034	if( isAgg && pSub->pOrderBy ) return 0; /* Restriction (16) */
sl@0	3035
sl@0	3036	/* Restriction 3: If the subquery is a join, make sure the subquery is
sl@0	3037	** not used as the right operand of an outer join. Examples of why this
sl@0	3038	** is not allowed:
sl@0	3039	**
sl@0	3040	** t1 LEFT OUTER JOIN (t2 JOIN t3)
sl@0	3041	**
sl@0	3042	** If we flatten the above, we would get
sl@0	3043	**
sl@0	3044	** (t1 LEFT OUTER JOIN t2) JOIN t3
sl@0	3045	**
sl@0	3046	** which is not at all the same thing.
sl@0	3047	*/
sl@0	3048	if( pSubSrc->nSrc>1 && (pSubitem->jointype & JT_OUTER)!=0 ){
sl@0	3049	return 0;
sl@0	3050	}
sl@0	3051
sl@0	3052	/* Restriction 12: If the subquery is the right operand of a left outer
sl@0	3053	** join, make sure the subquery has no WHERE clause.
sl@0	3054	** An examples of why this is not allowed:
sl@0	3055	**
sl@0	3056	** t1 LEFT OUTER JOIN (SELECT * FROM t2 WHERE t2.x>0)
sl@0	3057	**
sl@0	3058	** If we flatten the above, we would get
sl@0	3059	**
sl@0	3060	** (t1 LEFT OUTER JOIN t2) WHERE t2.x>0
sl@0	3061	**
sl@0	3062	** But the t2.x>0 test will always fail on a NULL row of t2, which
sl@0	3063	** effectively converts the OUTER JOIN into an INNER JOIN.
sl@0	3064	*/
sl@0	3065	if( (pSubitem->jointype & JT_OUTER)!=0 && pSub->pWhere!=0 ){
sl@0	3066	return 0;
sl@0	3067	}
sl@0	3068
sl@0	3069	/* Restriction 17: If the sub-query is a compound SELECT, then it must
sl@0	3070	** use only the UNION ALL operator. And none of the simple select queries
sl@0	3071	** that make up the compound SELECT are allowed to be aggregate or distinct
sl@0	3072	** queries.
sl@0	3073	*/
sl@0	3074	if( pSub->pPrior ){
sl@0	3075	if( p->pPrior \|\| isAgg \|\| p->isDistinct \|\| pSrc->nSrc!=1 ){
sl@0	3076	return 0;
sl@0	3077	}
sl@0	3078	for(pSub1=pSub; pSub1; pSub1=pSub1->pPrior){
sl@0	3079	if( pSub1->isAgg \|\| pSub1->isDistinct
sl@0	3080	\|\| (pSub1->pPrior && pSub1->op!=TK_ALL)
sl@0	3081	\|\| !pSub1->pSrc \|\| pSub1->pSrc->nSrc!=1
sl@0	3082	){
sl@0	3083	return 0;
sl@0	3084	}
sl@0	3085	}
sl@0	3086
sl@0	3087	/* Restriction 18. */
sl@0	3088	if( p->pOrderBy ){
sl@0	3089	int ii;
sl@0	3090	for(ii=0; ii<p->pOrderBy->nExpr; ii++){
sl@0	3091	Expr *pExpr = p->pOrderBy->a[ii].pExpr;
sl@0	3092	if( pExpr->op!=TK_COLUMN \|\| pExpr->iTable!=iParent ){
sl@0	3093	return 0;
sl@0	3094	}
sl@0	3095	}
sl@0	3096	}
sl@0	3097	}
sl@0	3098
sl@0	3099	pParse->zAuthContext = pSubitem->zName;
sl@0	3100	sqlite3AuthCheck(pParse, SQLITE_SELECT, 0, 0, 0);
sl@0	3101	pParse->zAuthContext = zSavedAuthContext;
sl@0	3102
sl@0	3103	/* If the sub-query is a compound SELECT statement, then it must be
sl@0	3104	** a UNION ALL and the parent query must be of the form:
sl@0	3105	**
sl@0	3106	** SELECT <expr-list> FROM (<sub-query>) <where-clause>
sl@0	3107	**
sl@0	3108	** followed by any ORDER BY, LIMIT and/or OFFSET clauses. This block
sl@0	3109	** creates N copies of the parent query without any ORDER BY, LIMIT or
sl@0	3110	** OFFSET clauses and joins them to the left-hand-side of the original
sl@0	3111	** using UNION ALL operators. In this case N is the number of simple
sl@0	3112	** select statements in the compound sub-query.
sl@0	3113	*/
sl@0	3114	for(pSub=pSub->pPrior; pSub; pSub=pSub->pPrior){
sl@0	3115	Select *pNew;
sl@0	3116	ExprList *pOrderBy = p->pOrderBy;
sl@0	3117	Expr *pLimit = p->pLimit;
sl@0	3118	Expr *pOffset = p->pOffset;
sl@0	3119	Select *pPrior = p->pPrior;
sl@0	3120	p->pOrderBy = 0;
sl@0	3121	p->pSrc = 0;
sl@0	3122	p->pPrior = 0;
sl@0	3123	p->pLimit = 0;
sl@0	3124	pNew = sqlite3SelectDup(db, p);
sl@0	3125	pNew->pPrior = pPrior;
sl@0	3126	p->pPrior = pNew;
sl@0	3127	p->pOrderBy = pOrderBy;
sl@0	3128	p->op = TK_ALL;
sl@0	3129	p->pSrc = pSrc;
sl@0	3130	p->pLimit = pLimit;
sl@0	3131	p->pOffset = pOffset;
sl@0	3132	p->pRightmost = 0;
sl@0	3133	pNew->pRightmost = 0;
sl@0	3134	}
sl@0	3135
sl@0	3136	/* If we reach this point, it means flattening is permitted for the
sl@0	3137	** iFrom-th entry of the FROM clause in the outer query.
sl@0	3138	*/
sl@0	3139	pSub = pSub1 = pSubitem->pSelect;
sl@0	3140	for(pParent=p; pParent; pParent=pParent->pPrior, pSub=pSub->pPrior){
sl@0	3141	int nSubSrc = pSubSrc->nSrc;
sl@0	3142	int jointype = 0;
sl@0	3143	pSubSrc = pSub->pSrc;
sl@0	3144	pSrc = pParent->pSrc;
sl@0	3145
sl@0	3146	/* Move all of the FROM elements of the subquery into the
sl@0	3147	** the FROM clause of the outer query. Before doing this, remember
sl@0	3148	** the cursor number for the original outer query FROM element in
sl@0	3149	** iParent. The iParent cursor will never be used. Subsequent code
sl@0	3150	** will scan expressions looking for iParent references and replace
sl@0	3151	** those references with expressions that resolve to the subquery FROM
sl@0	3152	** elements we are now copying in.
sl@0	3153	*/
sl@0	3154	if( pSrc ){
sl@0	3155	pSubitem = &pSrc->a[iFrom];
sl@0	3156	nSubSrc = pSubSrc->nSrc;
sl@0	3157	jointype = pSubitem->jointype;
sl@0	3158	sqlite3DeleteTable(pSubitem->pTab);
sl@0	3159	sqlite3DbFree(db, pSubitem->zDatabase);
sl@0	3160	sqlite3DbFree(db, pSubitem->zName);
sl@0	3161	sqlite3DbFree(db, pSubitem->zAlias);
sl@0	3162	pSubitem->pTab = 0;
sl@0	3163	pSubitem->zDatabase = 0;
sl@0	3164	pSubitem->zName = 0;
sl@0	3165	pSubitem->zAlias = 0;
sl@0	3166	}
sl@0	3167	if( nSubSrc!=1 \|\| !pSrc ){
sl@0	3168	int extra = nSubSrc - 1;
sl@0	3169	for(i=(pSrc?1:0); i<nSubSrc; i++){
sl@0	3170	pSrc = sqlite3SrcListAppend(db, pSrc, 0, 0);
sl@0	3171	if( pSrc==0 ){
sl@0	3172	pParent->pSrc = 0;
sl@0	3173	return 1;
sl@0	3174	}
sl@0	3175	}
sl@0	3176	pParent->pSrc = pSrc;
sl@0	3177	for(i=pSrc->nSrc-1; i-extra>=iFrom; i--){
sl@0	3178	pSrc->a[i] = pSrc->a[i-extra];
sl@0	3179	}
sl@0	3180	}
sl@0	3181	for(i=0; i<nSubSrc; i++){
sl@0	3182	pSrc->a[i+iFrom] = pSubSrc->a[i];
sl@0	3183	memset(&pSubSrc->a[i], 0, sizeof(pSubSrc->a[i]));
sl@0	3184	}
sl@0	3185	pSrc->a[iFrom].jointype = jointype;
sl@0	3186
sl@0	3187	/* Now begin substituting subquery result set expressions for
sl@0	3188	** references to the iParent in the outer query.
sl@0	3189	**
sl@0	3190	** Example:
sl@0	3191	**
sl@0	3192	** SELECT a+5, b10 FROM (SELECT x3 AS a, y+10 AS b FROM t1) WHERE a>b;
sl@0	3193	** \ \_____________ subquery __________/ /
sl@0	3194	** \_____________________ outer query ______________________________/
sl@0	3195	**
sl@0	3196	** We look at every expression in the outer query and every place we see
sl@0	3197	** "a" we substitute "x*3" and every place we see "b" we substitute "y+10".
sl@0	3198	*/
sl@0	3199	pList = pParent->pEList;
sl@0	3200	for(i=0; i<pList->nExpr; i++){
sl@0	3201	Expr *pExpr;
sl@0	3202	if( pList->a[i].zName==0 && (pExpr = pList->a[i].pExpr)->span.z!=0 ){
sl@0	3203	pList->a[i].zName =
sl@0	3204	sqlite3DbStrNDup(db, (char*)pExpr->span.z, pExpr->span.n);
sl@0	3205	}
sl@0	3206	}
sl@0	3207	substExprList(db, pParent->pEList, iParent, pSub->pEList);
sl@0	3208	if( isAgg ){
sl@0	3209	substExprList(db, pParent->pGroupBy, iParent, pSub->pEList);
sl@0	3210	substExpr(db, pParent->pHaving, iParent, pSub->pEList);
sl@0	3211	}
sl@0	3212	if( pSub->pOrderBy ){
sl@0	3213	assert( pParent->pOrderBy==0 );
sl@0	3214	pParent->pOrderBy = pSub->pOrderBy;
sl@0	3215	pSub->pOrderBy = 0;
sl@0	3216	}else if( pParent->pOrderBy ){
sl@0	3217	substExprList(db, pParent->pOrderBy, iParent, pSub->pEList);
sl@0	3218	}
sl@0	3219	if( pSub->pWhere ){
sl@0	3220	pWhere = sqlite3ExprDup(db, pSub->pWhere);
sl@0	3221	}else{
sl@0	3222	pWhere = 0;
sl@0	3223	}
sl@0	3224	if( subqueryIsAgg ){
sl@0	3225	assert( pParent->pHaving==0 );
sl@0	3226	pParent->pHaving = pParent->pWhere;
sl@0	3227	pParent->pWhere = pWhere;
sl@0	3228	substExpr(db, pParent->pHaving, iParent, pSub->pEList);
sl@0	3229	pParent->pHaving = sqlite3ExprAnd(db, pParent->pHaving,
sl@0	3230	sqlite3ExprDup(db, pSub->pHaving));
sl@0	3231	assert( pParent->pGroupBy==0 );
sl@0	3232	pParent->pGroupBy = sqlite3ExprListDup(db, pSub->pGroupBy);
sl@0	3233	}else{
sl@0	3234	substExpr(db, pParent->pWhere, iParent, pSub->pEList);
sl@0	3235	pParent->pWhere = sqlite3ExprAnd(db, pParent->pWhere, pWhere);
sl@0	3236	}
sl@0	3237
sl@0	3238	/* The flattened query is distinct if either the inner or the
sl@0	3239	** outer query is distinct.
sl@0	3240	*/
sl@0	3241	pParent->isDistinct = pParent->isDistinct \|\| pSub->isDistinct;
sl@0	3242
sl@0	3243	/*
sl@0	3244	** SELECT ... FROM (SELECT ... LIMIT a OFFSET b) LIMIT x OFFSET y;
sl@0	3245	**
sl@0	3246	** One is tempted to try to add a and b to combine the limits. But this
sl@0	3247	** does not work if either limit is negative.
sl@0	3248	*/
sl@0	3249	if( pSub->pLimit ){
sl@0	3250	pParent->pLimit = pSub->pLimit;
sl@0	3251	pSub->pLimit = 0;
sl@0	3252	}
sl@0	3253	}
sl@0	3254
sl@0	3255	/* Finially, delete what is left of the subquery and return
sl@0	3256	** success.
sl@0	3257	*/
sl@0	3258	sqlite3SelectDelete(db, pSub1);
sl@0	3259
sl@0	3260	return 1;
sl@0	3261	}
sl@0	3262	#endif /* !defined(SQLITE_OMIT_SUBQUERY) \|\| !defined(SQLITE_OMIT_VIEW) */
sl@0	3263
sl@0	3264	/*
sl@0	3265	** Analyze the SELECT statement passed as an argument to see if it
sl@0	3266	** is a min() or max() query. Return WHERE_ORDERBY_MIN or WHERE_ORDERBY_MAX if
sl@0	3267	** it is, or 0 otherwise. At present, a query is considered to be
sl@0	3268	** a min()/max() query if:
sl@0	3269	**
sl@0	3270	** 1. There is a single object in the FROM clause.
sl@0	3271	**
sl@0	3272	** 2. There is a single expression in the result set, and it is
sl@0	3273	** either min(x) or max(x), where x is a column reference.
sl@0	3274	*/
sl@0	3275	static int minMaxQuery(Parse pParse, Select p){
sl@0	3276	Expr *pExpr;
sl@0	3277	ExprList *pEList = p->pEList;
sl@0	3278
sl@0	3279	if( pEList->nExpr!=1 ) return WHERE_ORDERBY_NORMAL;
sl@0	3280	pExpr = pEList->a[0].pExpr;
sl@0	3281	pEList = pExpr->pList;
sl@0	3282	if( pExpr->op!=TK_AGG_FUNCTION \|\| pEList==0 \|\| pEList->nExpr!=1 ) return 0;
sl@0	3283	if( pEList->a[0].pExpr->op!=TK_AGG_COLUMN ) return WHERE_ORDERBY_NORMAL;
sl@0	3284	if( pExpr->token.n!=3 ) return WHERE_ORDERBY_NORMAL;
sl@0	3285	if( sqlite3StrNICmp((char*)pExpr->token.z,"min",3)==0 ){
sl@0	3286	return WHERE_ORDERBY_MIN;
sl@0	3287	}else if( sqlite3StrNICmp((char*)pExpr->token.z,"max",3)==0 ){
sl@0	3288	return WHERE_ORDERBY_MAX;
sl@0	3289	}
sl@0	3290	return WHERE_ORDERBY_NORMAL;
sl@0	3291	}
sl@0	3292
sl@0	3293	/*
sl@0	3294	** This routine resolves any names used in the result set of the
sl@0	3295	** supplied SELECT statement. If the SELECT statement being resolved
sl@0	3296	** is a sub-select, then pOuterNC is a pointer to the NameContext
sl@0	3297	** of the parent SELECT.
sl@0	3298	*/
sl@0	3299	int sqlite3SelectResolve(
sl@0	3300	Parse pParse, / The parser context */
sl@0	3301	Select p, / The SELECT statement being coded. */
sl@0	3302	NameContext pOuterNC / The outer name context. May be NULL. */
sl@0	3303	){
sl@0	3304	ExprList pEList; / Result set. */
sl@0	3305	int i; /* For-loop variable used in multiple places */
sl@0	3306	NameContext sNC; /* Local name-context */
sl@0	3307	ExprList pGroupBy; / The group by clause */
sl@0	3308
sl@0	3309	/* If this routine has run before, return immediately. */
sl@0	3310	if( p->isResolved ){
sl@0	3311	assert( !pOuterNC );
sl@0	3312	return SQLITE_OK;
sl@0	3313	}
sl@0	3314	p->isResolved = 1;
sl@0	3315
sl@0	3316	/* If there have already been errors, do nothing. */
sl@0	3317	if( pParse->nErr>0 ){
sl@0	3318	return SQLITE_ERROR;
sl@0	3319	}
sl@0	3320
sl@0	3321	/* Prepare the select statement. This call will allocate all cursors
sl@0	3322	** required to handle the tables and subqueries in the FROM clause.
sl@0	3323	*/
sl@0	3324	if( prepSelectStmt(pParse, p) ){
sl@0	3325	return SQLITE_ERROR;
sl@0	3326	}
sl@0	3327
sl@0	3328	/* Resolve the expressions in the LIMIT and OFFSET clauses. These
sl@0	3329	** are not allowed to refer to any names, so pass an empty NameContext.
sl@0	3330	*/
sl@0	3331	memset(&sNC, 0, sizeof(sNC));
sl@0	3332	sNC.pParse = pParse;
sl@0	3333	if( sqlite3ExprResolveNames(&sNC, p->pLimit) \|\|
sl@0	3334	sqlite3ExprResolveNames(&sNC, p->pOffset) ){
sl@0	3335	return SQLITE_ERROR;
sl@0	3336	}
sl@0	3337
sl@0	3338	/* Set up the local name-context to pass to ExprResolveNames() to
sl@0	3339	** resolve the expression-list.
sl@0	3340	*/
sl@0	3341	sNC.allowAgg = 1;
sl@0	3342	sNC.pSrcList = p->pSrc;
sl@0	3343	sNC.pNext = pOuterNC;
sl@0	3344
sl@0	3345	/* Resolve names in the result set. */
sl@0	3346	pEList = p->pEList;
sl@0	3347	if( !pEList ) return SQLITE_ERROR;
sl@0	3348	for(i=0; i<pEList->nExpr; i++){
sl@0	3349	Expr *pX = pEList->a[i].pExpr;
sl@0	3350	if( sqlite3ExprResolveNames(&sNC, pX) ){
sl@0	3351	return SQLITE_ERROR;
sl@0	3352	}
sl@0	3353	}
sl@0	3354
sl@0	3355	/* If there are no aggregate functions in the result-set, and no GROUP BY
sl@0	3356	** expression, do not allow aggregates in any of the other expressions.
sl@0	3357	*/
sl@0	3358	assert( !p->isAgg );
sl@0	3359	pGroupBy = p->pGroupBy;
sl@0	3360	if( pGroupBy \|\| sNC.hasAgg ){
sl@0	3361	p->isAgg = 1;
sl@0	3362	}else{
sl@0	3363	sNC.allowAgg = 0;
sl@0	3364	}
sl@0	3365
sl@0	3366	/* If a HAVING clause is present, then there must be a GROUP BY clause.
sl@0	3367	*/
sl@0	3368	if( p->pHaving && !pGroupBy ){
sl@0	3369	sqlite3ErrorMsg(pParse, "a GROUP BY clause is required before HAVING");
sl@0	3370	return SQLITE_ERROR;
sl@0	3371	}
sl@0	3372
sl@0	3373	/* Add the expression list to the name-context before parsing the
sl@0	3374	** other expressions in the SELECT statement. This is so that
sl@0	3375	** expressions in the WHERE clause (etc.) can refer to expressions by
sl@0	3376	** aliases in the result set.
sl@0	3377	**
sl@0	3378	** Minor point: If this is the case, then the expression will be
sl@0	3379	** re-evaluated for each reference to it.
sl@0	3380	*/
sl@0	3381	sNC.pEList = p->pEList;
sl@0	3382	if( sqlite3ExprResolveNames(&sNC, p->pWhere) \|\|
sl@0	3383	sqlite3ExprResolveNames(&sNC, p->pHaving) ){
sl@0	3384	return SQLITE_ERROR;
sl@0	3385	}
sl@0	3386	if( p->pPrior==0 ){
sl@0	3387	if( processOrderGroupBy(pParse, p, p->pOrderBy, 1, &sNC.hasAgg) ){
sl@0	3388	return SQLITE_ERROR;
sl@0	3389	}
sl@0	3390	}
sl@0	3391	if( processOrderGroupBy(pParse, p, pGroupBy, 0, &sNC.hasAgg) ){
sl@0	3392	return SQLITE_ERROR;
sl@0	3393	}
sl@0	3394
sl@0	3395	if( pParse->db->mallocFailed ){
sl@0	3396	return SQLITE_NOMEM;
sl@0	3397	}
sl@0	3398
sl@0	3399	/* Make sure the GROUP BY clause does not contain aggregate functions.
sl@0	3400	*/
sl@0	3401	if( pGroupBy ){
sl@0	3402	struct ExprList_item *pItem;
sl@0	3403
sl@0	3404	for(i=0, pItem=pGroupBy->a; i<pGroupBy->nExpr; i++, pItem++){
sl@0	3405	if( ExprHasProperty(pItem->pExpr, EP_Agg) ){
sl@0	3406	sqlite3ErrorMsg(pParse, "aggregate functions are not allowed in "
sl@0	3407	"the GROUP BY clause");
sl@0	3408	return SQLITE_ERROR;
sl@0	3409	}
sl@0	3410	}
sl@0	3411	}
sl@0	3412
sl@0	3413	/* If this is one SELECT of a compound, be sure to resolve names
sl@0	3414	** in the other SELECTs.
sl@0	3415	*/
sl@0	3416	if( p->pPrior ){
sl@0	3417	return sqlite3SelectResolve(pParse, p->pPrior, pOuterNC);
sl@0	3418	}else{
sl@0	3419	return SQLITE_OK;
sl@0	3420	}
sl@0	3421	}
sl@0	3422
sl@0	3423	/*
sl@0	3424	** Reset the aggregate accumulator.
sl@0	3425	**
sl@0	3426	** The aggregate accumulator is a set of memory cells that hold
sl@0	3427	** intermediate results while calculating an aggregate. This
sl@0	3428	** routine simply stores NULLs in all of those memory cells.
sl@0	3429	*/
sl@0	3430	static void resetAccumulator(Parse pParse, AggInfo pAggInfo){
sl@0	3431	Vdbe *v = pParse->pVdbe;
sl@0	3432	int i;
sl@0	3433	struct AggInfo_func *pFunc;
sl@0	3434	if( pAggInfo->nFunc+pAggInfo->nColumn==0 ){
sl@0	3435	return;
sl@0	3436	}
sl@0	3437	for(i=0; i<pAggInfo->nColumn; i++){
sl@0	3438	sqlite3VdbeAddOp2(v, OP_Null, 0, pAggInfo->aCol[i].iMem);
sl@0	3439	}
sl@0	3440	for(pFunc=pAggInfo->aFunc, i=0; i<pAggInfo->nFunc; i++, pFunc++){
sl@0	3441	sqlite3VdbeAddOp2(v, OP_Null, 0, pFunc->iMem);
sl@0	3442	if( pFunc->iDistinct>=0 ){
sl@0	3443	Expr *pE = pFunc->pExpr;
sl@0	3444	if( pE->pList==0 \|\| pE->pList->nExpr!=1 ){
sl@0	3445	sqlite3ErrorMsg(pParse, "DISTINCT in aggregate must be followed "
sl@0	3446	"by an expression");
sl@0	3447	pFunc->iDistinct = -1;
sl@0	3448	}else{
sl@0	3449	KeyInfo *pKeyInfo = keyInfoFromExprList(pParse, pE->pList);
sl@0	3450	sqlite3VdbeAddOp4(v, OP_OpenEphemeral, pFunc->iDistinct, 0, 0,
sl@0	3451	(char*)pKeyInfo, P4_KEYINFO_HANDOFF);
sl@0	3452	}
sl@0	3453	}
sl@0	3454	}
sl@0	3455	}
sl@0	3456
sl@0	3457	/*
sl@0	3458	** Invoke the OP_AggFinalize opcode for every aggregate function
sl@0	3459	** in the AggInfo structure.
sl@0	3460	*/
sl@0	3461	static void finalizeAggFunctions(Parse pParse, AggInfo pAggInfo){
sl@0	3462	Vdbe *v = pParse->pVdbe;
sl@0	3463	int i;
sl@0	3464	struct AggInfo_func *pF;
sl@0	3465	for(i=0, pF=pAggInfo->aFunc; i<pAggInfo->nFunc; i++, pF++){
sl@0	3466	ExprList *pList = pF->pExpr->pList;
sl@0	3467	sqlite3VdbeAddOp4(v, OP_AggFinal, pF->iMem, pList ? pList->nExpr : 0, 0,
sl@0	3468	(void*)pF->pFunc, P4_FUNCDEF);
sl@0	3469	}
sl@0	3470	}
sl@0	3471
sl@0	3472	/*
sl@0	3473	** Update the accumulator memory cells for an aggregate based on
sl@0	3474	** the current cursor position.
sl@0	3475	*/
sl@0	3476	static void updateAccumulator(Parse pParse, AggInfo pAggInfo){
sl@0	3477	Vdbe *v = pParse->pVdbe;
sl@0	3478	int i;
sl@0	3479	struct AggInfo_func *pF;
sl@0	3480	struct AggInfo_col *pC;
sl@0	3481
sl@0	3482	pAggInfo->directMode = 1;
sl@0	3483	for(i=0, pF=pAggInfo->aFunc; i<pAggInfo->nFunc; i++, pF++){
sl@0	3484	int nArg;
sl@0	3485	int addrNext = 0;
sl@0	3486	int regAgg;
sl@0	3487	ExprList *pList = pF->pExpr->pList;
sl@0	3488	if( pList ){
sl@0	3489	nArg = pList->nExpr;
sl@0	3490	regAgg = sqlite3GetTempRange(pParse, nArg);
sl@0	3491	sqlite3ExprCodeExprList(pParse, pList, regAgg, 0);
sl@0	3492	}else{
sl@0	3493	nArg = 0;
sl@0	3494	regAgg = 0;
sl@0	3495	}
sl@0	3496	if( pF->iDistinct>=0 ){
sl@0	3497	addrNext = sqlite3VdbeMakeLabel(v);
sl@0	3498	assert( nArg==1 );
sl@0	3499	codeDistinct(pParse, pF->iDistinct, addrNext, 1, regAgg);
sl@0	3500	}
sl@0	3501	if( pF->pFunc->needCollSeq ){
sl@0	3502	CollSeq *pColl = 0;
sl@0	3503	struct ExprList_item *pItem;
sl@0	3504	int j;
sl@0	3505	assert( pList!=0 ); /* pList!=0 if pF->pFunc->needCollSeq is true */
sl@0	3506	for(j=0, pItem=pList->a; !pColl && j<nArg; j++, pItem++){
sl@0	3507	pColl = sqlite3ExprCollSeq(pParse, pItem->pExpr);
sl@0	3508	}
sl@0	3509	if( !pColl ){
sl@0	3510	pColl = pParse->db->pDfltColl;
sl@0	3511	}
sl@0	3512	sqlite3VdbeAddOp4(v, OP_CollSeq, 0, 0, 0, (char *)pColl, P4_COLLSEQ);
sl@0	3513	}
sl@0	3514	sqlite3VdbeAddOp4(v, OP_AggStep, 0, regAgg, pF->iMem,
sl@0	3515	(void*)pF->pFunc, P4_FUNCDEF);
sl@0	3516	sqlite3VdbeChangeP5(v, nArg);
sl@0	3517	sqlite3ReleaseTempRange(pParse, regAgg, nArg);
sl@0	3518	sqlite3ExprCacheAffinityChange(pParse, regAgg, nArg);
sl@0	3519	if( addrNext ){
sl@0	3520	sqlite3VdbeResolveLabel(v, addrNext);
sl@0	3521	}
sl@0	3522	}
sl@0	3523	for(i=0, pC=pAggInfo->aCol; i<pAggInfo->nAccumulator; i++, pC++){
sl@0	3524	sqlite3ExprCode(pParse, pC->pExpr, pC->iMem);
sl@0	3525	}
sl@0	3526	pAggInfo->directMode = 0;
sl@0	3527	}
sl@0	3528
sl@0	3529	/*
sl@0	3530	** Generate code for the given SELECT statement.
sl@0	3531	**
sl@0	3532	** The results are distributed in various ways depending on the
sl@0	3533	** contents of the SelectDest structure pointed to by argument pDest
sl@0	3534	** as follows:
sl@0	3535	**
sl@0	3536	** pDest->eDest Result
sl@0	3537	** ------------ -------------------------------------------
sl@0	3538	** SRT_Callback Invoke the callback for each row of the result.
sl@0	3539	**
sl@0	3540	** SRT_Mem Store first result in memory cell pDest->iParm
sl@0	3541	**
sl@0	3542	** SRT_Set Store results as keys of table pDest->iParm.
sl@0	3543	** Apply the affinity pDest->affinity before storing them.
sl@0	3544	**
sl@0	3545	** SRT_Union Store results as a key in a temporary table pDest->iParm.
sl@0	3546	**
sl@0	3547	** SRT_Except Remove results from the temporary table pDest->iParm.
sl@0	3548	**
sl@0	3549	** SRT_Table Store results in temporary table pDest->iParm
sl@0	3550	**
sl@0	3551	** SRT_EphemTab Create an temporary table pDest->iParm and store
sl@0	3552	** the result there. The cursor is left open after
sl@0	3553	** returning.
sl@0	3554	**
sl@0	3555	** SRT_Coroutine Invoke a co-routine to compute a single row of
sl@0	3556	** the result
sl@0	3557	**
sl@0	3558	** SRT_Exists Store a 1 in memory cell pDest->iParm if the result
sl@0	3559	** set is not empty.
sl@0	3560	**
sl@0	3561	** SRT_Discard Throw the results away.
sl@0	3562	**
sl@0	3563	** See the selectInnerLoop() function for a canonical listing of the
sl@0	3564	** allowed values of eDest and their meanings.
sl@0	3565	**
sl@0	3566	** This routine returns the number of errors. If any errors are
sl@0	3567	** encountered, then an appropriate error message is left in
sl@0	3568	** pParse->zErrMsg.
sl@0	3569	**
sl@0	3570	** This routine does NOT free the Select structure passed in. The
sl@0	3571	** calling function needs to do that.
sl@0	3572	**
sl@0	3573	** The pParent, parentTab, and *pParentAgg fields are filled in if this
sl@0	3574	** SELECT is a subquery. This routine may try to combine this SELECT
sl@0	3575	** with its parent to form a single flat query. In so doing, it might
sl@0	3576	** change the parent query from a non-aggregate to an aggregate query.
sl@0	3577	** For that reason, the pParentAgg flag is passed as a pointer, so it
sl@0	3578	** can be changed.
sl@0	3579	**
sl@0	3580	** Example 1: The meaning of the pParent parameter.
sl@0	3581	**
sl@0	3582	** SELECT * FROM t1 JOIN (SELECT x, count(*) FROM t2) JOIN t3;
sl@0	3583	** \ \_______ subquery _______/ /
sl@0	3584	** \ /
sl@0	3585	** \____________________ outer query ___________________/
sl@0	3586	**
sl@0	3587	** This routine is called for the outer query first. For that call,
sl@0	3588	** pParent will be NULL. During the processing of the outer query, this
sl@0	3589	** routine is called recursively to handle the subquery. For the recursive
sl@0	3590	** call, pParent will point to the outer query. Because the subquery is
sl@0	3591	** the second element in a three-way join, the parentTab parameter will
sl@0	3592	** be 1 (the 2nd value of a 0-indexed array.)
sl@0	3593	*/
sl@0	3594	int sqlite3Select(
sl@0	3595	Parse pParse, / The parser context */
sl@0	3596	Select p, / The SELECT statement being coded. */
sl@0	3597	SelectDest pDest, / What to do with the query results */
sl@0	3598	Select pParent, / Another SELECT for which this is a sub-query */
sl@0	3599	int parentTab, /* Index in pParent->pSrc of this query */
sl@0	3600	int pParentAgg / True if pParent uses aggregate functions */
sl@0	3601	){
sl@0	3602	int i, j; /* Loop counters */
sl@0	3603	WhereInfo pWInfo; / Return from sqlite3WhereBegin() */
sl@0	3604	Vdbe v; / The virtual machine under construction */
sl@0	3605	int isAgg; /* True for select lists like "count()" /
sl@0	3606	ExprList pEList; / List of columns to extract. */
sl@0	3607	SrcList pTabList; / List of tables to select from */
sl@0	3608	Expr pWhere; / The WHERE clause. May be NULL */
sl@0	3609	ExprList pOrderBy; / The ORDER BY clause. May be NULL */
sl@0	3610	ExprList pGroupBy; / The GROUP BY clause. May be NULL */
sl@0	3611	Expr pHaving; / The HAVING clause. May be NULL */
sl@0	3612	int isDistinct; /* True if the DISTINCT keyword is present */
sl@0	3613	int distinct; /* Table to use for the distinct set */
sl@0	3614	int rc = 1; /* Value to return from this function */
sl@0	3615	int addrSortIndex; /* Address of an OP_OpenEphemeral instruction */
sl@0	3616	AggInfo sAggInfo; /* Information used by aggregate queries */
sl@0	3617	int iEnd; /* Address of the end of the query */
sl@0	3618	sqlite3 db; / The database connection */
sl@0	3619
sl@0	3620	db = pParse->db;
sl@0	3621	if( p==0 \|\| db->mallocFailed \|\| pParse->nErr ){
sl@0	3622	return 1;
sl@0	3623	}
sl@0	3624	if( sqlite3AuthCheck(pParse, SQLITE_SELECT, 0, 0, 0) ) return 1;
sl@0	3625	memset(&sAggInfo, 0, sizeof(sAggInfo));
sl@0	3626
sl@0	3627	pOrderBy = p->pOrderBy;
sl@0	3628	if( IgnorableOrderby(pDest) ){
sl@0	3629	p->pOrderBy = 0;
sl@0	3630
sl@0	3631	/* In these cases the DISTINCT operator makes no difference to the
sl@0	3632	** results, so remove it if it were specified.
sl@0	3633	*/
sl@0	3634	assert(pDest->eDest==SRT_Exists \|\| pDest->eDest==SRT_Union \|\|
sl@0	3635	pDest->eDest==SRT_Except \|\| pDest->eDest==SRT_Discard);
sl@0	3636	p->isDistinct = 0;
sl@0	3637	}
sl@0	3638	if( sqlite3SelectResolve(pParse, p, 0) ){
sl@0	3639	goto select_end;
sl@0	3640	}
sl@0	3641	p->pOrderBy = pOrderBy;
sl@0	3642
sl@0	3643
sl@0	3644	/* Make local copies of the parameters for this query.
sl@0	3645	*/
sl@0	3646	pTabList = p->pSrc;
sl@0	3647	isAgg = p->isAgg;
sl@0	3648	pEList = p->pEList;
sl@0	3649	if( pEList==0 ) goto select_end;
sl@0	3650
sl@0	3651	/*
sl@0	3652	** Do not even attempt to generate any code if we have already seen
sl@0	3653	** errors before this routine starts.
sl@0	3654	*/
sl@0	3655	if( pParse->nErr>0 ) goto select_end;
sl@0	3656
sl@0	3657	/* ORDER BY is ignored for some destinations.
sl@0	3658	*/
sl@0	3659	if( IgnorableOrderby(pDest) ){
sl@0	3660	pOrderBy = 0;
sl@0	3661	}
sl@0	3662
sl@0	3663	/* Begin generating code.
sl@0	3664	*/
sl@0	3665	v = sqlite3GetVdbe(pParse);
sl@0	3666	if( v==0 ) goto select_end;
sl@0	3667
sl@0	3668	/* Generate code for all sub-queries in the FROM clause
sl@0	3669	*/
sl@0	3670	#if !defined(SQLITE_OMIT_SUBQUERY) \|\| !defined(SQLITE_OMIT_VIEW)
sl@0	3671	for(i=0; !p->pPrior && i<pTabList->nSrc; i++){
sl@0	3672	struct SrcList_item *pItem = &pTabList->a[i];
sl@0	3673	SelectDest dest;
sl@0	3674	Select *pSub = pItem->pSelect;
sl@0	3675	int isAggSub;
sl@0	3676	char *zName = pItem->zName;
sl@0	3677
sl@0	3678	if( pSub==0 \|\| pItem->isPopulated ) continue;
sl@0	3679	if( zName!=0 ){ /* An sql view */
sl@0	3680	const char *zSavedAuthContext = pParse->zAuthContext;
sl@0	3681	pParse->zAuthContext = zName;
sl@0	3682	rc = sqlite3SelectResolve(pParse, pSub, 0);
sl@0	3683	pParse->zAuthContext = zSavedAuthContext;
sl@0	3684	if( rc ){
sl@0	3685	goto select_end;
sl@0	3686	}
sl@0	3687	}
sl@0	3688
sl@0	3689	/* Increment Parse.nHeight by the height of the largest expression
sl@0	3690	** tree refered to by this, the parent select. The child select
sl@0	3691	** may contain expression trees of at most
sl@0	3692	** (SQLITE_MAX_EXPR_DEPTH-Parse.nHeight) height. This is a bit
sl@0	3693	** more conservative than necessary, but much easier than enforcing
sl@0	3694	** an exact limit.
sl@0	3695	*/
sl@0	3696	pParse->nHeight += sqlite3SelectExprHeight(p);
sl@0	3697
sl@0	3698	/* Check to see if the subquery can be absorbed into the parent. */
sl@0	3699	isAggSub = pSub->isAgg;
sl@0	3700	if( flattenSubquery(pParse, p, i, isAgg, isAggSub) ){
sl@0	3701	if( isAggSub ){
sl@0	3702	p->isAgg = isAgg = 1;
sl@0	3703	}
sl@0	3704	i = -1;
sl@0	3705	}else{
sl@0	3706	sqlite3SelectDestInit(&dest, SRT_EphemTab, pItem->iCursor);
sl@0	3707	sqlite3Select(pParse, pSub, &dest, p, i, &isAgg);
sl@0	3708	}
sl@0	3709	if( pParse->nErr \|\| db->mallocFailed ){
sl@0	3710	goto select_end;
sl@0	3711	}
sl@0	3712	pParse->nHeight -= sqlite3SelectExprHeight(p);
sl@0	3713	pTabList = p->pSrc;
sl@0	3714	if( !IgnorableOrderby(pDest) ){
sl@0	3715	pOrderBy = p->pOrderBy;
sl@0	3716	}
sl@0	3717	}
sl@0	3718	pEList = p->pEList;
sl@0	3719	#endif
sl@0	3720	pWhere = p->pWhere;
sl@0	3721	pGroupBy = p->pGroupBy;
sl@0	3722	pHaving = p->pHaving;
sl@0	3723	isDistinct = p->isDistinct;
sl@0	3724
sl@0	3725	#ifndef SQLITE_OMIT_COMPOUND_SELECT
sl@0	3726	/* If there is are a sequence of queries, do the earlier ones first.
sl@0	3727	*/
sl@0	3728	if( p->pPrior ){
sl@0	3729	if( p->pRightmost==0 ){
sl@0	3730	Select pLoop, pRight = 0;
sl@0	3731	int cnt = 0;
sl@0	3732	int mxSelect;
sl@0	3733	for(pLoop=p; pLoop; pLoop=pLoop->pPrior, cnt++){
sl@0	3734	pLoop->pRightmost = p;
sl@0	3735	pLoop->pNext = pRight;
sl@0	3736	pRight = pLoop;
sl@0	3737	}
sl@0	3738	mxSelect = db->aLimit[SQLITE_LIMIT_COMPOUND_SELECT];
sl@0	3739	if( mxSelect && cnt>mxSelect ){
sl@0	3740	sqlite3ErrorMsg(pParse, "too many terms in compound SELECT");
sl@0	3741	return 1;
sl@0	3742	}
sl@0	3743	}
sl@0	3744	return multiSelect(pParse, p, pDest);
sl@0	3745	}
sl@0	3746	#endif
sl@0	3747
sl@0	3748	/* If writing to memory or generating a set
sl@0	3749	** only a single column may be output.
sl@0	3750	*/
sl@0	3751	#ifndef SQLITE_OMIT_SUBQUERY
sl@0	3752	if( checkForMultiColumnSelectError(pParse, pDest, pEList->nExpr) ){
sl@0	3753	goto select_end;
sl@0	3754	}
sl@0	3755	#endif
sl@0	3756
sl@0	3757	/* If possible, rewrite the query to use GROUP BY instead of DISTINCT.
sl@0	3758	** GROUP BY may use an index, DISTINCT never does.
sl@0	3759	*/
sl@0	3760	if( p->isDistinct && !p->isAgg && !p->pGroupBy ){
sl@0	3761	p->pGroupBy = sqlite3ExprListDup(db, p->pEList);
sl@0	3762	pGroupBy = p->pGroupBy;
sl@0	3763	p->isDistinct = 0;
sl@0	3764	isDistinct = 0;
sl@0	3765	}
sl@0	3766
sl@0	3767	/* If there is an ORDER BY clause, then this sorting
sl@0	3768	** index might end up being unused if the data can be
sl@0	3769	** extracted in pre-sorted order. If that is the case, then the
sl@0	3770	** OP_OpenEphemeral instruction will be changed to an OP_Noop once
sl@0	3771	** we figure out that the sorting index is not needed. The addrSortIndex
sl@0	3772	** variable is used to facilitate that change.
sl@0	3773	*/
sl@0	3774	if( pOrderBy ){
sl@0	3775	KeyInfo *pKeyInfo;
sl@0	3776	pKeyInfo = keyInfoFromExprList(pParse, pOrderBy);
sl@0	3777	pOrderBy->iECursor = pParse->nTab++;
sl@0	3778	p->addrOpenEphm[2] = addrSortIndex =
sl@0	3779	sqlite3VdbeAddOp4(v, OP_OpenEphemeral,
sl@0	3780	pOrderBy->iECursor, pOrderBy->nExpr+2, 0,
sl@0	3781	(char*)pKeyInfo, P4_KEYINFO_HANDOFF);
sl@0	3782	}else{
sl@0	3783	addrSortIndex = -1;
sl@0	3784	}
sl@0	3785
sl@0	3786	/* If the output is destined for a temporary table, open that table.
sl@0	3787	*/
sl@0	3788	if( pDest->eDest==SRT_EphemTab ){
sl@0	3789	sqlite3VdbeAddOp2(v, OP_OpenEphemeral, pDest->iParm, pEList->nExpr);
sl@0	3790	}
sl@0	3791
sl@0	3792	/* Set the limiter.
sl@0	3793	*/
sl@0	3794	iEnd = sqlite3VdbeMakeLabel(v);
sl@0	3795	computeLimitRegisters(pParse, p, iEnd);
sl@0	3796
sl@0	3797	/* Open a virtual index to use for the distinct set.
sl@0	3798	*/
sl@0	3799	if( isDistinct ){
sl@0	3800	KeyInfo *pKeyInfo;
sl@0	3801	assert( isAgg \|\| pGroupBy );
sl@0	3802	distinct = pParse->nTab++;
sl@0	3803	pKeyInfo = keyInfoFromExprList(pParse, p->pEList);
sl@0	3804	sqlite3VdbeAddOp4(v, OP_OpenEphemeral, distinct, 0, 0,
sl@0	3805	(char*)pKeyInfo, P4_KEYINFO_HANDOFF);
sl@0	3806	}else{
sl@0	3807	distinct = -1;
sl@0	3808	}
sl@0	3809
sl@0	3810	/* Aggregate and non-aggregate queries are handled differently */
sl@0	3811	if( !isAgg && pGroupBy==0 ){
sl@0	3812	/* This case is for non-aggregate queries
sl@0	3813	** Begin the database scan
sl@0	3814	*/
sl@0	3815	pWInfo = sqlite3WhereBegin(pParse, pTabList, pWhere, &pOrderBy, 0);
sl@0	3816	if( pWInfo==0 ) goto select_end;
sl@0	3817
sl@0	3818	/* If sorting index that was created by a prior OP_OpenEphemeral
sl@0	3819	** instruction ended up not being needed, then change the OP_OpenEphemeral
sl@0	3820	** into an OP_Noop.
sl@0	3821	*/
sl@0	3822	if( addrSortIndex>=0 && pOrderBy==0 ){
sl@0	3823	sqlite3VdbeChangeToNoop(v, addrSortIndex, 1);
sl@0	3824	p->addrOpenEphm[2] = -1;
sl@0	3825	}
sl@0	3826
sl@0	3827	/* Use the standard inner loop
sl@0	3828	*/
sl@0	3829	assert(!isDistinct);
sl@0	3830	selectInnerLoop(pParse, p, pEList, 0, 0, pOrderBy, -1, pDest,
sl@0	3831	pWInfo->iContinue, pWInfo->iBreak);
sl@0	3832
sl@0	3833	/* End the database scan loop.
sl@0	3834	*/
sl@0	3835	sqlite3WhereEnd(pWInfo);
sl@0	3836	}else{
sl@0	3837	/* This is the processing for aggregate queries */
sl@0	3838	NameContext sNC; /* Name context for processing aggregate information */
sl@0	3839	int iAMem; /* First Mem address for storing current GROUP BY */
sl@0	3840	int iBMem; /* First Mem address for previous GROUP BY */
sl@0	3841	int iUseFlag; /* Mem address holding flag indicating that at least
sl@0	3842	** one row of the input to the aggregator has been
sl@0	3843	** processed */
sl@0	3844	int iAbortFlag; /* Mem address which causes query abort if positive */
sl@0	3845	int groupBySort; /* Rows come from source in GROUP BY order */
sl@0	3846
sl@0	3847
sl@0	3848	/* The following variables hold addresses or labels for parts of the
sl@0	3849	** virtual machine program we are putting together */
sl@0	3850	int addrOutputRow; /* Start of subroutine that outputs a result row */
sl@0	3851	int regOutputRow; /* Return address register for output subroutine */
sl@0	3852	int addrSetAbort; /* Set the abort flag and return */
sl@0	3853	int addrInitializeLoop; /* Start of code that initializes the input loop */
sl@0	3854	int addrTopOfLoop; /* Top of the input loop */
sl@0	3855	int addrEnd; /* End of all processing */
sl@0	3856	int addrSortingIdx; /* The OP_OpenEphemeral for the sorting index */
sl@0	3857	int addrReset; /* Subroutine for resetting the accumulator */
sl@0	3858	int regReset; /* Return address register for reset subroutine */
sl@0	3859
sl@0	3860	addrEnd = sqlite3VdbeMakeLabel(v);
sl@0	3861
sl@0	3862	/* Convert TK_COLUMN nodes into TK_AGG_COLUMN and make entries in
sl@0	3863	** sAggInfo for all TK_AGG_FUNCTION nodes in expressions of the
sl@0	3864	** SELECT statement.
sl@0	3865	*/
sl@0	3866	memset(&sNC, 0, sizeof(sNC));
sl@0	3867	sNC.pParse = pParse;
sl@0	3868	sNC.pSrcList = pTabList;
sl@0	3869	sNC.pAggInfo = &sAggInfo;
sl@0	3870	sAggInfo.nSortingColumn = pGroupBy ? pGroupBy->nExpr+1 : 0;
sl@0	3871	sAggInfo.pGroupBy = pGroupBy;
sl@0	3872	sqlite3ExprAnalyzeAggList(&sNC, pEList);
sl@0	3873	sqlite3ExprAnalyzeAggList(&sNC, pOrderBy);
sl@0	3874	if( pHaving ){
sl@0	3875	sqlite3ExprAnalyzeAggregates(&sNC, pHaving);
sl@0	3876	}
sl@0	3877	sAggInfo.nAccumulator = sAggInfo.nColumn;
sl@0	3878	for(i=0; i<sAggInfo.nFunc; i++){
sl@0	3879	sqlite3ExprAnalyzeAggList(&sNC, sAggInfo.aFunc[i].pExpr->pList);
sl@0	3880	}
sl@0	3881	if( db->mallocFailed ) goto select_end;
sl@0	3882
sl@0	3883	/* Processing for aggregates with GROUP BY is very different and
sl@0	3884	** much more complex than aggregates without a GROUP BY.
sl@0	3885	*/
sl@0	3886	if( pGroupBy ){
sl@0	3887	KeyInfo pKeyInfo; / Keying information for the group by clause */
sl@0	3888	int j1;
sl@0	3889
sl@0	3890	/* Create labels that we will be needing
sl@0	3891	*/
sl@0	3892	addrInitializeLoop = sqlite3VdbeMakeLabel(v);
sl@0	3893
sl@0	3894	/* If there is a GROUP BY clause we might need a sorting index to
sl@0	3895	** implement it. Allocate that sorting index now. If it turns out
sl@0	3896	** that we do not need it after all, the OpenEphemeral instruction
sl@0	3897	** will be converted into a Noop.
sl@0	3898	*/
sl@0	3899	sAggInfo.sortingIdx = pParse->nTab++;
sl@0	3900	pKeyInfo = keyInfoFromExprList(pParse, pGroupBy);
sl@0	3901	addrSortingIdx = sqlite3VdbeAddOp4(v, OP_OpenEphemeral,
sl@0	3902	sAggInfo.sortingIdx, sAggInfo.nSortingColumn,
sl@0	3903	0, (char*)pKeyInfo, P4_KEYINFO_HANDOFF);
sl@0	3904
sl@0	3905	/* Initialize memory locations used by GROUP BY aggregate processing
sl@0	3906	*/
sl@0	3907	iUseFlag = ++pParse->nMem;
sl@0	3908	iAbortFlag = ++pParse->nMem;
sl@0	3909	iAMem = pParse->nMem + 1;
sl@0	3910	pParse->nMem += pGroupBy->nExpr;
sl@0	3911	iBMem = pParse->nMem + 1;
sl@0	3912	pParse->nMem += pGroupBy->nExpr;
sl@0	3913	sqlite3VdbeAddOp2(v, OP_Integer, 0, iAbortFlag);
sl@0	3914	VdbeComment((v, "clear abort flag"));
sl@0	3915	sqlite3VdbeAddOp2(v, OP_Integer, 0, iUseFlag);
sl@0	3916	VdbeComment((v, "indicate accumulator empty"));
sl@0	3917	sqlite3VdbeAddOp2(v, OP_Goto, 0, addrInitializeLoop);
sl@0	3918
sl@0	3919	/* Generate a subroutine that outputs a single row of the result
sl@0	3920	** set. This subroutine first looks at the iUseFlag. If iUseFlag
sl@0	3921	** is less than or equal to zero, the subroutine is a no-op. If
sl@0	3922	** the processing calls for the query to abort, this subroutine
sl@0	3923	** increments the iAbortFlag memory location before returning in
sl@0	3924	** order to signal the caller to abort.
sl@0	3925	*/
sl@0	3926	addrSetAbort = sqlite3VdbeCurrentAddr(v);
sl@0	3927	sqlite3VdbeAddOp2(v, OP_Integer, 1, iAbortFlag);
sl@0	3928	VdbeComment((v, "set abort flag"));
sl@0	3929	regOutputRow = ++pParse->nMem;
sl@0	3930	sqlite3VdbeAddOp1(v, OP_Return, regOutputRow);
sl@0	3931	addrOutputRow = sqlite3VdbeCurrentAddr(v);
sl@0	3932	sqlite3VdbeAddOp2(v, OP_IfPos, iUseFlag, addrOutputRow+2);
sl@0	3933	VdbeComment((v, "Groupby result generator entry point"));
sl@0	3934	sqlite3VdbeAddOp1(v, OP_Return, regOutputRow);
sl@0	3935	finalizeAggFunctions(pParse, &sAggInfo);
sl@0	3936	if( pHaving ){
sl@0	3937	sqlite3ExprIfFalse(pParse, pHaving, addrOutputRow+1, SQLITE_JUMPIFNULL);
sl@0	3938	}
sl@0	3939	selectInnerLoop(pParse, p, p->pEList, 0, 0, pOrderBy,
sl@0	3940	distinct, pDest,
sl@0	3941	addrOutputRow+1, addrSetAbort);
sl@0	3942	sqlite3VdbeAddOp1(v, OP_Return, regOutputRow);
sl@0	3943	VdbeComment((v, "end groupby result generator"));
sl@0	3944
sl@0	3945	/* Generate a subroutine that will reset the group-by accumulator
sl@0	3946	*/
sl@0	3947	addrReset = sqlite3VdbeCurrentAddr(v);
sl@0	3948	regReset = ++pParse->nMem;
sl@0	3949	resetAccumulator(pParse, &sAggInfo);
sl@0	3950	sqlite3VdbeAddOp1(v, OP_Return, regReset);
sl@0	3951
sl@0	3952	/* Begin a loop that will extract all source rows in GROUP BY order.
sl@0	3953	** This might involve two separate loops with an OP_Sort in between, or
sl@0	3954	** it might be a single loop that uses an index to extract information
sl@0	3955	** in the right order to begin with.
sl@0	3956	*/
sl@0	3957	sqlite3VdbeResolveLabel(v, addrInitializeLoop);
sl@0	3958	sqlite3VdbeAddOp2(v, OP_Gosub, regReset, addrReset);
sl@0	3959	pWInfo = sqlite3WhereBegin(pParse, pTabList, pWhere, &pGroupBy, 0);
sl@0	3960	if( pWInfo==0 ) goto select_end;
sl@0	3961	if( pGroupBy==0 ){
sl@0	3962	/* The optimizer is able to deliver rows in group by order so
sl@0	3963	** we do not have to sort. The OP_OpenEphemeral table will be
sl@0	3964	** cancelled later because we still need to use the pKeyInfo
sl@0	3965	*/
sl@0	3966	pGroupBy = p->pGroupBy;
sl@0	3967	groupBySort = 0;
sl@0	3968	}else{
sl@0	3969	/* Rows are coming out in undetermined order. We have to push
sl@0	3970	** each row into a sorting index, terminate the first loop,
sl@0	3971	** then loop over the sorting index in order to get the output
sl@0	3972	** in sorted order
sl@0	3973	*/
sl@0	3974	int regBase;
sl@0	3975	int regRecord;
sl@0	3976	int nCol;
sl@0	3977	int nGroupBy;
sl@0	3978
sl@0	3979	groupBySort = 1;
sl@0	3980	nGroupBy = pGroupBy->nExpr;
sl@0	3981	nCol = nGroupBy + 1;
sl@0	3982	j = nGroupBy+1;
sl@0	3983	for(i=0; i<sAggInfo.nColumn; i++){
sl@0	3984	if( sAggInfo.aCol[i].iSorterColumn>=j ){
sl@0	3985	nCol++;
sl@0	3986	j++;
sl@0	3987	}
sl@0	3988	}
sl@0	3989	regBase = sqlite3GetTempRange(pParse, nCol);
sl@0	3990	sqlite3ExprCodeExprList(pParse, pGroupBy, regBase, 0);
sl@0	3991	sqlite3VdbeAddOp2(v, OP_Sequence, sAggInfo.sortingIdx,regBase+nGroupBy);
sl@0	3992	j = nGroupBy+1;
sl@0	3993	for(i=0; i<sAggInfo.nColumn; i++){
sl@0	3994	struct AggInfo_col *pCol = &sAggInfo.aCol[i];
sl@0	3995	if( pCol->iSorterColumn>=j ){
sl@0	3996	int r1 = j + regBase;
sl@0	3997	#ifndef NDEBUG
sl@0	3998	int r2 =
sl@0	3999	#endif
sl@0	4000	sqlite3ExprCodeGetColumn(pParse,
sl@0	4001	pCol->pTab, pCol->iColumn, pCol->iTable, r1, 0);
sl@0	4002	j++;
sl@0	4003
sl@0	4004	/* sAggInfo.aCol[] only contains one entry per column. So
sl@0	4005	** The reference to pCol->iColumn,pCol->iTable must have been
sl@0	4006	** the first reference to that column. Hence,
sl@0	4007	** sqliteExprCodeGetColumn is guaranteed to put the result in
sl@0	4008	** the column requested.
sl@0	4009	*/
sl@0	4010	assert( r1==r2 );
sl@0	4011	}
sl@0	4012	}
sl@0	4013	regRecord = sqlite3GetTempReg(pParse);
sl@0	4014	sqlite3VdbeAddOp3(v, OP_MakeRecord, regBase, nCol, regRecord);
sl@0	4015	sqlite3VdbeAddOp2(v, OP_IdxInsert, sAggInfo.sortingIdx, regRecord);
sl@0	4016	sqlite3ReleaseTempReg(pParse, regRecord);
sl@0	4017	sqlite3ReleaseTempRange(pParse, regBase, nCol);
sl@0	4018	sqlite3WhereEnd(pWInfo);
sl@0	4019	sqlite3VdbeAddOp2(v, OP_Sort, sAggInfo.sortingIdx, addrEnd);
sl@0	4020	VdbeComment((v, "GROUP BY sort"));
sl@0	4021	sAggInfo.useSortingIdx = 1;
sl@0	4022	}
sl@0	4023
sl@0	4024	/* Evaluate the current GROUP BY terms and store in b0, b1, b2...
sl@0	4025	** (b0 is memory location iBMem+0, b1 is iBMem+1, and so forth)
sl@0	4026	** Then compare the current GROUP BY terms against the GROUP BY terms
sl@0	4027	** from the previous row currently stored in a0, a1, a2...
sl@0	4028	*/
sl@0	4029	addrTopOfLoop = sqlite3VdbeCurrentAddr(v);
sl@0	4030	for(j=0; j<pGroupBy->nExpr; j++){
sl@0	4031	if( groupBySort ){
sl@0	4032	sqlite3VdbeAddOp3(v, OP_Column, sAggInfo.sortingIdx, j, iBMem+j);
sl@0	4033	}else{
sl@0	4034	sAggInfo.directMode = 1;
sl@0	4035	sqlite3ExprCode(pParse, pGroupBy->a[j].pExpr, iBMem+j);
sl@0	4036	}
sl@0	4037	}
sl@0	4038	sqlite3VdbeAddOp4(v, OP_Compare, iAMem, iBMem, pGroupBy->nExpr,
sl@0	4039	(char*)pKeyInfo, P4_KEYINFO);
sl@0	4040	j1 = sqlite3VdbeCurrentAddr(v);
sl@0	4041	sqlite3VdbeAddOp3(v, OP_Jump, j1+1, 0, j1+1);
sl@0	4042
sl@0	4043	/* Generate code that runs whenever the GROUP BY changes.
sl@0	4044	** Changes in the GROUP BY are detected by the previous code
sl@0	4045	** block. If there were no changes, this block is skipped.
sl@0	4046	**
sl@0	4047	** This code copies current group by terms in b0,b1,b2,...
sl@0	4048	** over to a0,a1,a2. It then calls the output subroutine
sl@0	4049	** and resets the aggregate accumulator registers in preparation
sl@0	4050	** for the next GROUP BY batch.
sl@0	4051	*/
sl@0	4052	sqlite3ExprCodeMove(pParse, iBMem, iAMem, pGroupBy->nExpr);
sl@0	4053	sqlite3VdbeAddOp2(v, OP_Gosub, regOutputRow, addrOutputRow);
sl@0	4054	VdbeComment((v, "output one row"));
sl@0	4055	sqlite3VdbeAddOp2(v, OP_IfPos, iAbortFlag, addrEnd);
sl@0	4056	VdbeComment((v, "check abort flag"));
sl@0	4057	sqlite3VdbeAddOp2(v, OP_Gosub, regReset, addrReset);
sl@0	4058	VdbeComment((v, "reset accumulator"));
sl@0	4059
sl@0	4060	/* Update the aggregate accumulators based on the content of
sl@0	4061	** the current row
sl@0	4062	*/
sl@0	4063	sqlite3VdbeJumpHere(v, j1);
sl@0	4064	updateAccumulator(pParse, &sAggInfo);
sl@0	4065	sqlite3VdbeAddOp2(v, OP_Integer, 1, iUseFlag);
sl@0	4066	VdbeComment((v, "indicate data in accumulator"));
sl@0	4067
sl@0	4068	/* End of the loop
sl@0	4069	*/
sl@0	4070	if( groupBySort ){
sl@0	4071	sqlite3VdbeAddOp2(v, OP_Next, sAggInfo.sortingIdx, addrTopOfLoop);
sl@0	4072	}else{
sl@0	4073	sqlite3WhereEnd(pWInfo);
sl@0	4074	sqlite3VdbeChangeToNoop(v, addrSortingIdx, 1);
sl@0	4075	}
sl@0	4076
sl@0	4077	/* Output the final row of result
sl@0	4078	*/
sl@0	4079	sqlite3VdbeAddOp2(v, OP_Gosub, regOutputRow, addrOutputRow);
sl@0	4080	VdbeComment((v, "output final row"));
sl@0	4081
sl@0	4082	} /* endif pGroupBy */
sl@0	4083	else {
sl@0	4084	ExprList *pMinMax = 0;
sl@0	4085	ExprList *pDel = 0;
sl@0	4086	u8 flag;
sl@0	4087
sl@0	4088	/* Check if the query is of one of the following forms:
sl@0	4089	**
sl@0	4090	** SELECT min(x) FROM ...
sl@0	4091	** SELECT max(x) FROM ...
sl@0	4092	**
sl@0	4093	** If it is, then ask the code in where.c to attempt to sort results
sl@0	4094	** as if there was an "ORDER ON x" or "ORDER ON x DESC" clause.
sl@0	4095	** If where.c is able to produce results sorted in this order, then
sl@0	4096	** add vdbe code to break out of the processing loop after the
sl@0	4097	** first iteration (since the first iteration of the loop is
sl@0	4098	** guaranteed to operate on the row with the minimum or maximum
sl@0	4099	** value of x, the only row required).
sl@0	4100	**
sl@0	4101	** A special flag must be passed to sqlite3WhereBegin() to slightly
sl@0	4102	** modify behaviour as follows:
sl@0	4103	**
sl@0	4104	** + If the query is a "SELECT min(x)", then the loop coded by
sl@0	4105	** where.c should not iterate over any values with a NULL value
sl@0	4106	** for x.
sl@0	4107	**
sl@0	4108	** + The optimizer code in where.c (the thing that decides which
sl@0	4109	** index or indices to use) should place a different priority on
sl@0	4110	** satisfying the 'ORDER BY' clause than it does in other cases.
sl@0	4111	** Refer to code and comments in where.c for details.
sl@0	4112	*/
sl@0	4113	flag = minMaxQuery(pParse, p);
sl@0	4114	if( flag ){
sl@0	4115	pDel = pMinMax = sqlite3ExprListDup(db, p->pEList->a[0].pExpr->pList);
sl@0	4116	if( pMinMax && !db->mallocFailed ){
sl@0	4117	pMinMax->a[0].sortOrder = flag!=WHERE_ORDERBY_MIN;
sl@0	4118	pMinMax->a[0].pExpr->op = TK_COLUMN;
sl@0	4119	}
sl@0	4120	}
sl@0	4121
sl@0	4122	/* This case runs if the aggregate has no GROUP BY clause. The
sl@0	4123	** processing is much simpler since there is only a single row
sl@0	4124	** of output.
sl@0	4125	*/
sl@0	4126	resetAccumulator(pParse, &sAggInfo);
sl@0	4127	pWInfo = sqlite3WhereBegin(pParse, pTabList, pWhere, &pMinMax, flag);
sl@0	4128	if( pWInfo==0 ){
sl@0	4129	sqlite3ExprListDelete(db, pDel);
sl@0	4130	goto select_end;
sl@0	4131	}
sl@0	4132	updateAccumulator(pParse, &sAggInfo);
sl@0	4133	if( !pMinMax && flag ){
sl@0	4134	sqlite3VdbeAddOp2(v, OP_Goto, 0, pWInfo->iBreak);
sl@0	4135	VdbeComment((v, "%s() by index",(flag==WHERE_ORDERBY_MIN?"min":"max")));
sl@0	4136	}
sl@0	4137	sqlite3WhereEnd(pWInfo);
sl@0	4138	finalizeAggFunctions(pParse, &sAggInfo);
sl@0	4139	pOrderBy = 0;
sl@0	4140	if( pHaving ){
sl@0	4141	sqlite3ExprIfFalse(pParse, pHaving, addrEnd, SQLITE_JUMPIFNULL);
sl@0	4142	}
sl@0	4143	selectInnerLoop(pParse, p, p->pEList, 0, 0, 0, -1,
sl@0	4144	pDest, addrEnd, addrEnd);
sl@0	4145
sl@0	4146	sqlite3ExprListDelete(db, pDel);
sl@0	4147	}
sl@0	4148	sqlite3VdbeResolveLabel(v, addrEnd);
sl@0	4149
sl@0	4150	} /* endif aggregate query */
sl@0	4151
sl@0	4152	/* If there is an ORDER BY clause, then we need to sort the results
sl@0	4153	** and send them to the callback one by one.
sl@0	4154	*/
sl@0	4155	if( pOrderBy ){
sl@0	4156	generateSortTail(pParse, p, v, pEList->nExpr, pDest);
sl@0	4157	}
sl@0	4158
sl@0	4159	#ifndef SQLITE_OMIT_SUBQUERY
sl@0	4160	/* If this was a subquery, we have now converted the subquery into a
sl@0	4161	** temporary table. So set the SrcList_item.isPopulated flag to prevent
sl@0	4162	** this subquery from being evaluated again and to force the use of
sl@0	4163	** the temporary table.
sl@0	4164	*/
sl@0	4165	if( pParent ){
sl@0	4166	assert( pParent->pSrc->nSrc>parentTab );
sl@0	4167	assert( pParent->pSrc->a[parentTab].pSelect==p );
sl@0	4168	pParent->pSrc->a[parentTab].isPopulated = 1;
sl@0	4169	}
sl@0	4170	#endif
sl@0	4171
sl@0	4172	/* Jump here to skip this query
sl@0	4173	*/
sl@0	4174	sqlite3VdbeResolveLabel(v, iEnd);
sl@0	4175
sl@0	4176	/* The SELECT was successfully coded. Set the return code to 0
sl@0	4177	** to indicate no errors.
sl@0	4178	*/
sl@0	4179	rc = 0;
sl@0	4180
sl@0	4181	/* Control jumps to here if an error is encountered above, or upon
sl@0	4182	** successful coding of the SELECT.
sl@0	4183	*/
sl@0	4184	select_end:
sl@0	4185
sl@0	4186	/* Identify column names if we will be using them in a callback. This
sl@0	4187	** step is skipped if the output is going to some other destination.
sl@0	4188	*/
sl@0	4189	if( rc==SQLITE_OK && pDest->eDest==SRT_Callback ){
sl@0	4190	generateColumnNames(pParse, pTabList, pEList);
sl@0	4191	}
sl@0	4192
sl@0	4193	sqlite3DbFree(db, sAggInfo.aCol);
sl@0	4194	sqlite3DbFree(db, sAggInfo.aFunc);
sl@0	4195	return rc;
sl@0	4196	}
sl@0	4197
sl@0	4198	#if defined(SQLITE_DEBUG)
sl@0	4199	/*
sl@0	4200	*******************************************************************************
sl@0	4201	** The following code is used for testing and debugging only. The code
sl@0	4202	** that follows does not appear in normal builds.
sl@0	4203	**
sl@0	4204	** These routines are used to print out the content of all or part of a
sl@0	4205	** parse structures such as Select or Expr. Such printouts are useful
sl@0	4206	** for helping to understand what is happening inside the code generator
sl@0	4207	** during the execution of complex SELECT statements.
sl@0	4208	**
sl@0	4209	** These routine are not called anywhere from within the normal
sl@0	4210	** code base. Then are intended to be called from within the debugger
sl@0	4211	** or from temporary "printf" statements inserted for debugging.
sl@0	4212	*/
sl@0	4213	void sqlite3PrintExpr(Expr *p){
sl@0	4214	if( p->token.z && p->token.n>0 ){
sl@0	4215	sqlite3DebugPrintf("(%.*s", p->token.n, p->token.z);
sl@0	4216	}else{
sl@0	4217	sqlite3DebugPrintf("(%d", p->op);
sl@0	4218	}
sl@0	4219	if( p->pLeft ){
sl@0	4220	sqlite3DebugPrintf(" ");
sl@0	4221	sqlite3PrintExpr(p->pLeft);
sl@0	4222	}
sl@0	4223	if( p->pRight ){
sl@0	4224	sqlite3DebugPrintf(" ");
sl@0	4225	sqlite3PrintExpr(p->pRight);
sl@0	4226	}
sl@0	4227	sqlite3DebugPrintf(")");
sl@0	4228	}
sl@0	4229	void sqlite3PrintExprList(ExprList *pList){
sl@0	4230	int i;
sl@0	4231	for(i=0; i<pList->nExpr; i++){
sl@0	4232	sqlite3PrintExpr(pList->a[i].pExpr);
sl@0	4233	if( i<pList->nExpr-1 ){
sl@0	4234	sqlite3DebugPrintf(", ");
sl@0	4235	}
sl@0	4236	}
sl@0	4237	}
sl@0	4238	void sqlite3PrintSelect(Select *p, int indent){
sl@0	4239	sqlite3DebugPrintf("%*sSELECT(%p) ", indent, "", p);
sl@0	4240	sqlite3PrintExprList(p->pEList);
sl@0	4241	sqlite3DebugPrintf("\n");
sl@0	4242	if( p->pSrc ){
sl@0	4243	char *zPrefix;
sl@0	4244	int i;
sl@0	4245	zPrefix = "FROM";
sl@0	4246	for(i=0; i<p->pSrc->nSrc; i++){
sl@0	4247	struct SrcList_item *pItem = &p->pSrc->a[i];
sl@0	4248	sqlite3DebugPrintf("%*s ", indent+6, zPrefix);
sl@0	4249	zPrefix = "";
sl@0	4250	if( pItem->pSelect ){
sl@0	4251	sqlite3DebugPrintf("(\n");
sl@0	4252	sqlite3PrintSelect(pItem->pSelect, indent+10);
sl@0	4253	sqlite3DebugPrintf("%*s)", indent+8, "");
sl@0	4254	}else if( pItem->zName ){
sl@0	4255	sqlite3DebugPrintf("%s", pItem->zName);
sl@0	4256	}
sl@0	4257	if( pItem->pTab ){
sl@0	4258	sqlite3DebugPrintf("(table: %s)", pItem->pTab->zName);
sl@0	4259	}
sl@0	4260	if( pItem->zAlias ){
sl@0	4261	sqlite3DebugPrintf(" AS %s", pItem->zAlias);
sl@0	4262	}
sl@0	4263	if( i<p->pSrc->nSrc-1 ){
sl@0	4264	sqlite3DebugPrintf(",");
sl@0	4265	}
sl@0	4266	sqlite3DebugPrintf("\n");
sl@0	4267	}
sl@0	4268	}
sl@0	4269	if( p->pWhere ){
sl@0	4270	sqlite3DebugPrintf("%*s WHERE ", indent, "");
sl@0	4271	sqlite3PrintExpr(p->pWhere);
sl@0	4272	sqlite3DebugPrintf("\n");
sl@0	4273	}
sl@0	4274	if( p->pGroupBy ){
sl@0	4275	sqlite3DebugPrintf("%*s GROUP BY ", indent, "");
sl@0	4276	sqlite3PrintExprList(p->pGroupBy);
sl@0	4277	sqlite3DebugPrintf("\n");
sl@0	4278	}
sl@0	4279	if( p->pHaving ){
sl@0	4280	sqlite3DebugPrintf("%*s HAVING ", indent, "");
sl@0	4281	sqlite3PrintExpr(p->pHaving);
sl@0	4282	sqlite3DebugPrintf("\n");
sl@0	4283	}
sl@0	4284	if( p->pOrderBy ){
sl@0	4285	sqlite3DebugPrintf("%*s ORDER BY ", indent, "");
sl@0	4286	sqlite3PrintExprList(p->pOrderBy);
sl@0	4287	sqlite3DebugPrintf("\n");
sl@0	4288	}
sl@0	4289	}
sl@0	4290	/* End of the structure debug printing code
sl@0	4291	*****************************************************************************/
sl@0	4292	#endif /* defined(SQLITE_TEST) \|\| defined(SQLITE_DEBUG) */

author	sl
	Tue, 10 Jun 2014 14:32:02 +0200 (2014-06-10)
changeset 1	260cb5ec6c19
permissions	-rw-r--r--