000001 /*
000002 ** 2001 September 15
000003 **
000004 ** The author disclaims copyright to this source code. In place of
000005 ** a legal notice, here is a blessing:
000006 **
000007 ** May you do good and not evil.
000008 ** May you find forgiveness for yourself and forgive others.
000009 ** May you share freely, never taking more than you give.
000010 **
000011 *************************************************************************
000012 ** This file contains routines used for analyzing expressions and
000013 ** for generating VDBE code that evaluates expressions in SQLite.
000014 */
000015 #include "sqliteInt.h"
000016
000017 /* Forward declarations */
000018 static void exprCodeBetween(Parse*,Expr*,int,void(*)(Parse*,Expr*,int,int),int);
000019 static int exprCodeVector(Parse *pParse, Expr *p, int *piToFree);
000020
000021 /*
000022 ** Return the affinity character for a single column of a table.
000023 */
000024 char sqlite3TableColumnAffinity(Table *pTab, int iCol){
000025 assert( iCol<pTab->nCol );
000026 return iCol>=0 ? pTab->aCol[iCol].affinity : SQLITE_AFF_INTEGER;
000027 }
000028
000029 /*
000030 ** Return the 'affinity' of the expression pExpr if any.
000031 **
000032 ** If pExpr is a column, a reference to a column via an 'AS' alias,
000033 ** or a sub-select with a column as the return value, then the
000034 ** affinity of that column is returned. Otherwise, 0x00 is returned,
000035 ** indicating no affinity for the expression.
000036 **
000037 ** i.e. the WHERE clause expressions in the following statements all
000038 ** have an affinity:
000039 **
000040 ** CREATE TABLE t1(a);
000041 ** SELECT * FROM t1 WHERE a;
000042 ** SELECT a AS b FROM t1 WHERE b;
000043 ** SELECT * FROM t1 WHERE (select a from t1);
000044 */
000045 char sqlite3ExprAffinity(Expr *pExpr){
000046 int op;
000047 pExpr = sqlite3ExprSkipCollate(pExpr);
000048 if( pExpr->flags & EP_Generic ) return 0;
000049 op = pExpr->op;
000050 if( op==TK_SELECT ){
000051 assert( pExpr->flags&EP_xIsSelect );
000052 return sqlite3ExprAffinity(pExpr->x.pSelect->pEList->a[0].pExpr);
000053 }
000054 if( op==TK_REGISTER ) op = pExpr->op2;
000055 #ifndef SQLITE_OMIT_CAST
000056 if( op==TK_CAST ){
000057 assert( !ExprHasProperty(pExpr, EP_IntValue) );
000058 return sqlite3AffinityType(pExpr->u.zToken, 0);
000059 }
000060 #endif
000061 if( op==TK_AGG_COLUMN || op==TK_COLUMN ){
000062 return sqlite3TableColumnAffinity(pExpr->pTab, pExpr->iColumn);
000063 }
000064 if( op==TK_SELECT_COLUMN ){
000065 assert( pExpr->pLeft->flags&EP_xIsSelect );
000066 return sqlite3ExprAffinity(
000067 pExpr->pLeft->x.pSelect->pEList->a[pExpr->iColumn].pExpr
000068 );
000069 }
000070 return pExpr->affinity;
000071 }
000072
000073 /*
000074 ** Set the collating sequence for expression pExpr to be the collating
000075 ** sequence named by pToken. Return a pointer to a new Expr node that
000076 ** implements the COLLATE operator.
000077 **
000078 ** If a memory allocation error occurs, that fact is recorded in pParse->db
000079 ** and the pExpr parameter is returned unchanged.
000080 */
000081 Expr *sqlite3ExprAddCollateToken(
000082 Parse *pParse, /* Parsing context */
000083 Expr *pExpr, /* Add the "COLLATE" clause to this expression */
000084 const Token *pCollName, /* Name of collating sequence */
000085 int dequote /* True to dequote pCollName */
000086 ){
000087 if( pCollName->n>0 ){
000088 Expr *pNew = sqlite3ExprAlloc(pParse->db, TK_COLLATE, pCollName, dequote);
000089 if( pNew ){
000090 pNew->pLeft = pExpr;
000091 pNew->flags |= EP_Collate|EP_Skip;
000092 pExpr = pNew;
000093 }
000094 }
000095 return pExpr;
000096 }
000097 Expr *sqlite3ExprAddCollateString(Parse *pParse, Expr *pExpr, const char *zC){
000098 Token s;
000099 assert( zC!=0 );
000100 sqlite3TokenInit(&s, (char*)zC);
000101 return sqlite3ExprAddCollateToken(pParse, pExpr, &s, 0);
000102 }
000103
000104 /*
000105 ** Skip over any TK_COLLATE operators and any unlikely()
000106 ** or likelihood() function at the root of an expression.
000107 */
000108 Expr *sqlite3ExprSkipCollate(Expr *pExpr){
000109 while( pExpr && ExprHasProperty(pExpr, EP_Skip) ){
000110 if( ExprHasProperty(pExpr, EP_Unlikely) ){
000111 assert( !ExprHasProperty(pExpr, EP_xIsSelect) );
000112 assert( pExpr->x.pList->nExpr>0 );
000113 assert( pExpr->op==TK_FUNCTION );
000114 pExpr = pExpr->x.pList->a[0].pExpr;
000115 }else{
000116 assert( pExpr->op==TK_COLLATE );
000117 pExpr = pExpr->pLeft;
000118 }
000119 }
000120 return pExpr;
000121 }
000122
000123 /*
000124 ** Return the collation sequence for the expression pExpr. If
000125 ** there is no defined collating sequence, return NULL.
000126 **
000127 ** The collating sequence might be determined by a COLLATE operator
000128 ** or by the presence of a column with a defined collating sequence.
000129 ** COLLATE operators take first precedence. Left operands take
000130 ** precedence over right operands.
000131 */
000132 CollSeq *sqlite3ExprCollSeq(Parse *pParse, Expr *pExpr){
000133 sqlite3 *db = pParse->db;
000134 CollSeq *pColl = 0;
000135 Expr *p = pExpr;
000136 while( p ){
000137 int op = p->op;
000138 if( p->flags & EP_Generic ) break;
000139 if( op==TK_CAST || op==TK_UPLUS ){
000140 p = p->pLeft;
000141 continue;
000142 }
000143 if( op==TK_COLLATE || (op==TK_REGISTER && p->op2==TK_COLLATE) ){
000144 pColl = sqlite3GetCollSeq(pParse, ENC(db), 0, p->u.zToken);
000145 break;
000146 }
000147 if( (op==TK_AGG_COLUMN || op==TK_COLUMN
000148 || op==TK_REGISTER || op==TK_TRIGGER)
000149 && p->pTab!=0
000150 ){
000151 /* op==TK_REGISTER && p->pTab!=0 happens when pExpr was originally
000152 ** a TK_COLUMN but was previously evaluated and cached in a register */
000153 int j = p->iColumn;
000154 if( j>=0 ){
000155 const char *zColl = p->pTab->aCol[j].zColl;
000156 pColl = sqlite3FindCollSeq(db, ENC(db), zColl, 0);
000157 }
000158 break;
000159 }
000160 if( p->flags & EP_Collate ){
000161 if( p->pLeft && (p->pLeft->flags & EP_Collate)!=0 ){
000162 p = p->pLeft;
000163 }else{
000164 Expr *pNext = p->pRight;
000165 /* The Expr.x union is never used at the same time as Expr.pRight */
000166 assert( p->x.pList==0 || p->pRight==0 );
000167 /* p->flags holds EP_Collate and p->pLeft->flags does not. And
000168 ** p->x.pSelect cannot. So if p->x.pLeft exists, it must hold at
000169 ** least one EP_Collate. Thus the following two ALWAYS. */
000170 if( p->x.pList!=0 && ALWAYS(!ExprHasProperty(p, EP_xIsSelect)) ){
000171 int i;
000172 for(i=0; ALWAYS(i<p->x.pList->nExpr); i++){
000173 if( ExprHasProperty(p->x.pList->a[i].pExpr, EP_Collate) ){
000174 pNext = p->x.pList->a[i].pExpr;
000175 break;
000176 }
000177 }
000178 }
000179 p = pNext;
000180 }
000181 }else{
000182 break;
000183 }
000184 }
000185 if( sqlite3CheckCollSeq(pParse, pColl) ){
000186 pColl = 0;
000187 }
000188 return pColl;
000189 }
000190
000191 /*
000192 ** pExpr is an operand of a comparison operator. aff2 is the
000193 ** type affinity of the other operand. This routine returns the
000194 ** type affinity that should be used for the comparison operator.
000195 */
000196 char sqlite3CompareAffinity(Expr *pExpr, char aff2){
000197 char aff1 = sqlite3ExprAffinity(pExpr);
000198 if( aff1 && aff2 ){
000199 /* Both sides of the comparison are columns. If one has numeric
000200 ** affinity, use that. Otherwise use no affinity.
000201 */
000202 if( sqlite3IsNumericAffinity(aff1) || sqlite3IsNumericAffinity(aff2) ){
000203 return SQLITE_AFF_NUMERIC;
000204 }else{
000205 return SQLITE_AFF_BLOB;
000206 }
000207 }else if( !aff1 && !aff2 ){
000208 /* Neither side of the comparison is a column. Compare the
000209 ** results directly.
000210 */
000211 return SQLITE_AFF_BLOB;
000212 }else{
000213 /* One side is a column, the other is not. Use the columns affinity. */
000214 assert( aff1==0 || aff2==0 );
000215 return (aff1 + aff2);
000216 }
000217 }
000218
000219 /*
000220 ** pExpr is a comparison operator. Return the type affinity that should
000221 ** be applied to both operands prior to doing the comparison.
000222 */
000223 static char comparisonAffinity(Expr *pExpr){
000224 char aff;
000225 assert( pExpr->op==TK_EQ || pExpr->op==TK_IN || pExpr->op==TK_LT ||
000226 pExpr->op==TK_GT || pExpr->op==TK_GE || pExpr->op==TK_LE ||
000227 pExpr->op==TK_NE || pExpr->op==TK_IS || pExpr->op==TK_ISNOT );
000228 assert( pExpr->pLeft );
000229 aff = sqlite3ExprAffinity(pExpr->pLeft);
000230 if( pExpr->pRight ){
000231 aff = sqlite3CompareAffinity(pExpr->pRight, aff);
000232 }else if( ExprHasProperty(pExpr, EP_xIsSelect) ){
000233 aff = sqlite3CompareAffinity(pExpr->x.pSelect->pEList->a[0].pExpr, aff);
000234 }else if( NEVER(aff==0) ){
000235 aff = SQLITE_AFF_BLOB;
000236 }
000237 return aff;
000238 }
000239
000240 /*
000241 ** pExpr is a comparison expression, eg. '=', '<', IN(...) etc.
000242 ** idx_affinity is the affinity of an indexed column. Return true
000243 ** if the index with affinity idx_affinity may be used to implement
000244 ** the comparison in pExpr.
000245 */
000246 int sqlite3IndexAffinityOk(Expr *pExpr, char idx_affinity){
000247 char aff = comparisonAffinity(pExpr);
000248 switch( aff ){
000249 case SQLITE_AFF_BLOB:
000250 return 1;
000251 case SQLITE_AFF_TEXT:
000252 return idx_affinity==SQLITE_AFF_TEXT;
000253 default:
000254 return sqlite3IsNumericAffinity(idx_affinity);
000255 }
000256 }
000257
000258 /*
000259 ** Return the P5 value that should be used for a binary comparison
000260 ** opcode (OP_Eq, OP_Ge etc.) used to compare pExpr1 and pExpr2.
000261 */
000262 static u8 binaryCompareP5(Expr *pExpr1, Expr *pExpr2, int jumpIfNull){
000263 u8 aff = (char)sqlite3ExprAffinity(pExpr2);
000264 aff = (u8)sqlite3CompareAffinity(pExpr1, aff) | (u8)jumpIfNull;
000265 return aff;
000266 }
000267
000268 /*
000269 ** Return a pointer to the collation sequence that should be used by
000270 ** a binary comparison operator comparing pLeft and pRight.
000271 **
000272 ** If the left hand expression has a collating sequence type, then it is
000273 ** used. Otherwise the collation sequence for the right hand expression
000274 ** is used, or the default (BINARY) if neither expression has a collating
000275 ** type.
000276 **
000277 ** Argument pRight (but not pLeft) may be a null pointer. In this case,
000278 ** it is not considered.
000279 */
000280 CollSeq *sqlite3BinaryCompareCollSeq(
000281 Parse *pParse,
000282 Expr *pLeft,
000283 Expr *pRight
000284 ){
000285 CollSeq *pColl;
000286 assert( pLeft );
000287 if( pLeft->flags & EP_Collate ){
000288 pColl = sqlite3ExprCollSeq(pParse, pLeft);
000289 }else if( pRight && (pRight->flags & EP_Collate)!=0 ){
000290 pColl = sqlite3ExprCollSeq(pParse, pRight);
000291 }else{
000292 pColl = sqlite3ExprCollSeq(pParse, pLeft);
000293 if( !pColl ){
000294 pColl = sqlite3ExprCollSeq(pParse, pRight);
000295 }
000296 }
000297 return pColl;
000298 }
000299
000300 /*
000301 ** Generate code for a comparison operator.
000302 */
000303 static int codeCompare(
000304 Parse *pParse, /* The parsing (and code generating) context */
000305 Expr *pLeft, /* The left operand */
000306 Expr *pRight, /* The right operand */
000307 int opcode, /* The comparison opcode */
000308 int in1, int in2, /* Register holding operands */
000309 int dest, /* Jump here if true. */
000310 int jumpIfNull /* If true, jump if either operand is NULL */
000311 ){
000312 int p5;
000313 int addr;
000314 CollSeq *p4;
000315
000316 p4 = sqlite3BinaryCompareCollSeq(pParse, pLeft, pRight);
000317 p5 = binaryCompareP5(pLeft, pRight, jumpIfNull);
000318 addr = sqlite3VdbeAddOp4(pParse->pVdbe, opcode, in2, dest, in1,
000319 (void*)p4, P4_COLLSEQ);
000320 sqlite3VdbeChangeP5(pParse->pVdbe, (u8)p5);
000321 return addr;
000322 }
000323
000324 /*
000325 ** Return true if expression pExpr is a vector, or false otherwise.
000326 **
000327 ** A vector is defined as any expression that results in two or more
000328 ** columns of result. Every TK_VECTOR node is an vector because the
000329 ** parser will not generate a TK_VECTOR with fewer than two entries.
000330 ** But a TK_SELECT might be either a vector or a scalar. It is only
000331 ** considered a vector if it has two or more result columns.
000332 */
000333 int sqlite3ExprIsVector(Expr *pExpr){
000334 return sqlite3ExprVectorSize(pExpr)>1;
000335 }
000336
000337 /*
000338 ** If the expression passed as the only argument is of type TK_VECTOR
000339 ** return the number of expressions in the vector. Or, if the expression
000340 ** is a sub-select, return the number of columns in the sub-select. For
000341 ** any other type of expression, return 1.
000342 */
000343 int sqlite3ExprVectorSize(Expr *pExpr){
000344 u8 op = pExpr->op;
000345 if( op==TK_REGISTER ) op = pExpr->op2;
000346 if( op==TK_VECTOR ){
000347 return pExpr->x.pList->nExpr;
000348 }else if( op==TK_SELECT ){
000349 return pExpr->x.pSelect->pEList->nExpr;
000350 }else{
000351 return 1;
000352 }
000353 }
000354
000355 #ifndef SQLITE_OMIT_SUBQUERY
000356 /*
000357 ** Return a pointer to a subexpression of pVector that is the i-th
000358 ** column of the vector (numbered starting with 0). The caller must
000359 ** ensure that i is within range.
000360 **
000361 ** If pVector is really a scalar (and "scalar" here includes subqueries
000362 ** that return a single column!) then return pVector unmodified.
000363 **
000364 ** pVector retains ownership of the returned subexpression.
000365 **
000366 ** If the vector is a (SELECT ...) then the expression returned is
000367 ** just the expression for the i-th term of the result set, and may
000368 ** not be ready for evaluation because the table cursor has not yet
000369 ** been positioned.
000370 */
000371 Expr *sqlite3VectorFieldSubexpr(Expr *pVector, int i){
000372 assert( i<sqlite3ExprVectorSize(pVector) );
000373 if( sqlite3ExprIsVector(pVector) ){
000374 assert( pVector->op2==0 || pVector->op==TK_REGISTER );
000375 if( pVector->op==TK_SELECT || pVector->op2==TK_SELECT ){
000376 return pVector->x.pSelect->pEList->a[i].pExpr;
000377 }else{
000378 return pVector->x.pList->a[i].pExpr;
000379 }
000380 }
000381 return pVector;
000382 }
000383 #endif /* !defined(SQLITE_OMIT_SUBQUERY) */
000384
000385 #ifndef SQLITE_OMIT_SUBQUERY
000386 /*
000387 ** Compute and return a new Expr object which when passed to
000388 ** sqlite3ExprCode() will generate all necessary code to compute
000389 ** the iField-th column of the vector expression pVector.
000390 **
000391 ** It is ok for pVector to be a scalar (as long as iField==0).
000392 ** In that case, this routine works like sqlite3ExprDup().
000393 **
000394 ** The caller owns the returned Expr object and is responsible for
000395 ** ensuring that the returned value eventually gets freed.
000396 **
000397 ** The caller retains ownership of pVector. If pVector is a TK_SELECT,
000398 ** then the returned object will reference pVector and so pVector must remain
000399 ** valid for the life of the returned object. If pVector is a TK_VECTOR
000400 ** or a scalar expression, then it can be deleted as soon as this routine
000401 ** returns.
000402 **
000403 ** A trick to cause a TK_SELECT pVector to be deleted together with
000404 ** the returned Expr object is to attach the pVector to the pRight field
000405 ** of the returned TK_SELECT_COLUMN Expr object.
000406 */
000407 Expr *sqlite3ExprForVectorField(
000408 Parse *pParse, /* Parsing context */
000409 Expr *pVector, /* The vector. List of expressions or a sub-SELECT */
000410 int iField /* Which column of the vector to return */
000411 ){
000412 Expr *pRet;
000413 if( pVector->op==TK_SELECT ){
000414 assert( pVector->flags & EP_xIsSelect );
000415 /* The TK_SELECT_COLUMN Expr node:
000416 **
000417 ** pLeft: pVector containing TK_SELECT
000418 ** pRight: not used. But recursively deleted.
000419 ** iColumn: Index of a column in pVector
000420 ** pLeft->iTable: First in an array of register holding result, or 0
000421 ** if the result is not yet computed.
000422 **
000423 ** sqlite3ExprDelete() specifically skips the recursive delete of
000424 ** pLeft on TK_SELECT_COLUMN nodes. But pRight is followed, so pVector
000425 ** can be attached to pRight to cause this node to take ownership of
000426 ** pVector. Typically there will be multiple TK_SELECT_COLUMN nodes
000427 ** with the same pLeft pointer to the pVector, but only one of them
000428 ** will own the pVector.
000429 */
000430 pRet = sqlite3PExpr(pParse, TK_SELECT_COLUMN, 0, 0);
000431 if( pRet ){
000432 pRet->iColumn = iField;
000433 pRet->pLeft = pVector;
000434 }
000435 assert( pRet==0 || pRet->iTable==0 );
000436 }else{
000437 if( pVector->op==TK_VECTOR ) pVector = pVector->x.pList->a[iField].pExpr;
000438 pRet = sqlite3ExprDup(pParse->db, pVector, 0);
000439 }
000440 return pRet;
000441 }
000442 #endif /* !define(SQLITE_OMIT_SUBQUERY) */
000443
000444 /*
000445 ** If expression pExpr is of type TK_SELECT, generate code to evaluate
000446 ** it. Return the register in which the result is stored (or, if the
000447 ** sub-select returns more than one column, the first in an array
000448 ** of registers in which the result is stored).
000449 **
000450 ** If pExpr is not a TK_SELECT expression, return 0.
000451 */
000452 static int exprCodeSubselect(Parse *pParse, Expr *pExpr){
000453 int reg = 0;
000454 #ifndef SQLITE_OMIT_SUBQUERY
000455 if( pExpr->op==TK_SELECT ){
000456 reg = sqlite3CodeSubselect(pParse, pExpr, 0, 0);
000457 }
000458 #endif
000459 return reg;
000460 }
000461
000462 /*
000463 ** Argument pVector points to a vector expression - either a TK_VECTOR
000464 ** or TK_SELECT that returns more than one column. This function returns
000465 ** the register number of a register that contains the value of
000466 ** element iField of the vector.
000467 **
000468 ** If pVector is a TK_SELECT expression, then code for it must have
000469 ** already been generated using the exprCodeSubselect() routine. In this
000470 ** case parameter regSelect should be the first in an array of registers
000471 ** containing the results of the sub-select.
000472 **
000473 ** If pVector is of type TK_VECTOR, then code for the requested field
000474 ** is generated. In this case (*pRegFree) may be set to the number of
000475 ** a temporary register to be freed by the caller before returning.
000476 **
000477 ** Before returning, output parameter (*ppExpr) is set to point to the
000478 ** Expr object corresponding to element iElem of the vector.
000479 */
000480 static int exprVectorRegister(
000481 Parse *pParse, /* Parse context */
000482 Expr *pVector, /* Vector to extract element from */
000483 int iField, /* Field to extract from pVector */
000484 int regSelect, /* First in array of registers */
000485 Expr **ppExpr, /* OUT: Expression element */
000486 int *pRegFree /* OUT: Temp register to free */
000487 ){
000488 u8 op = pVector->op;
000489 assert( op==TK_VECTOR || op==TK_REGISTER || op==TK_SELECT );
000490 if( op==TK_REGISTER ){
000491 *ppExpr = sqlite3VectorFieldSubexpr(pVector, iField);
000492 return pVector->iTable+iField;
000493 }
000494 if( op==TK_SELECT ){
000495 *ppExpr = pVector->x.pSelect->pEList->a[iField].pExpr;
000496 return regSelect+iField;
000497 }
000498 *ppExpr = pVector->x.pList->a[iField].pExpr;
000499 return sqlite3ExprCodeTemp(pParse, *ppExpr, pRegFree);
000500 }
000501
000502 /*
000503 ** Expression pExpr is a comparison between two vector values. Compute
000504 ** the result of the comparison (1, 0, or NULL) and write that
000505 ** result into register dest.
000506 **
000507 ** The caller must satisfy the following preconditions:
000508 **
000509 ** if pExpr->op==TK_IS: op==TK_EQ and p5==SQLITE_NULLEQ
000510 ** if pExpr->op==TK_ISNOT: op==TK_NE and p5==SQLITE_NULLEQ
000511 ** otherwise: op==pExpr->op and p5==0
000512 */
000513 static void codeVectorCompare(
000514 Parse *pParse, /* Code generator context */
000515 Expr *pExpr, /* The comparison operation */
000516 int dest, /* Write results into this register */
000517 u8 op, /* Comparison operator */
000518 u8 p5 /* SQLITE_NULLEQ or zero */
000519 ){
000520 Vdbe *v = pParse->pVdbe;
000521 Expr *pLeft = pExpr->pLeft;
000522 Expr *pRight = pExpr->pRight;
000523 int nLeft = sqlite3ExprVectorSize(pLeft);
000524 int i;
000525 int regLeft = 0;
000526 int regRight = 0;
000527 u8 opx = op;
000528 int addrDone = sqlite3VdbeMakeLabel(v);
000529
000530 if( nLeft!=sqlite3ExprVectorSize(pRight) ){
000531 sqlite3ErrorMsg(pParse, "row value misused");
000532 return;
000533 }
000534 assert( pExpr->op==TK_EQ || pExpr->op==TK_NE
000535 || pExpr->op==TK_IS || pExpr->op==TK_ISNOT
000536 || pExpr->op==TK_LT || pExpr->op==TK_GT
000537 || pExpr->op==TK_LE || pExpr->op==TK_GE
000538 );
000539 assert( pExpr->op==op || (pExpr->op==TK_IS && op==TK_EQ)
000540 || (pExpr->op==TK_ISNOT && op==TK_NE) );
000541 assert( p5==0 || pExpr->op!=op );
000542 assert( p5==SQLITE_NULLEQ || pExpr->op==op );
000543
000544 p5 |= SQLITE_STOREP2;
000545 if( opx==TK_LE ) opx = TK_LT;
000546 if( opx==TK_GE ) opx = TK_GT;
000547
000548 regLeft = exprCodeSubselect(pParse, pLeft);
000549 regRight = exprCodeSubselect(pParse, pRight);
000550
000551 for(i=0; 1 /*Loop exits by "break"*/; i++){
000552 int regFree1 = 0, regFree2 = 0;
000553 Expr *pL, *pR;
000554 int r1, r2;
000555 assert( i>=0 && i<nLeft );
000556 if( i>0 ) sqlite3ExprCachePush(pParse);
000557 r1 = exprVectorRegister(pParse, pLeft, i, regLeft, &pL, ®Free1);
000558 r2 = exprVectorRegister(pParse, pRight, i, regRight, &pR, ®Free2);
000559 codeCompare(pParse, pL, pR, opx, r1, r2, dest, p5);
000560 testcase(op==OP_Lt); VdbeCoverageIf(v,op==OP_Lt);
000561 testcase(op==OP_Le); VdbeCoverageIf(v,op==OP_Le);
000562 testcase(op==OP_Gt); VdbeCoverageIf(v,op==OP_Gt);
000563 testcase(op==OP_Ge); VdbeCoverageIf(v,op==OP_Ge);
000564 testcase(op==OP_Eq); VdbeCoverageIf(v,op==OP_Eq);
000565 testcase(op==OP_Ne); VdbeCoverageIf(v,op==OP_Ne);
000566 sqlite3ReleaseTempReg(pParse, regFree1);
000567 sqlite3ReleaseTempReg(pParse, regFree2);
000568 if( i>0 ) sqlite3ExprCachePop(pParse);
000569 if( i==nLeft-1 ){
000570 break;
000571 }
000572 if( opx==TK_EQ ){
000573 sqlite3VdbeAddOp2(v, OP_IfNot, dest, addrDone); VdbeCoverage(v);
000574 p5 |= SQLITE_KEEPNULL;
000575 }else if( opx==TK_NE ){
000576 sqlite3VdbeAddOp2(v, OP_If, dest, addrDone); VdbeCoverage(v);
000577 p5 |= SQLITE_KEEPNULL;
000578 }else{
000579 assert( op==TK_LT || op==TK_GT || op==TK_LE || op==TK_GE );
000580 sqlite3VdbeAddOp2(v, OP_ElseNotEq, 0, addrDone);
000581 VdbeCoverageIf(v, op==TK_LT);
000582 VdbeCoverageIf(v, op==TK_GT);
000583 VdbeCoverageIf(v, op==TK_LE);
000584 VdbeCoverageIf(v, op==TK_GE);
000585 if( i==nLeft-2 ) opx = op;
000586 }
000587 }
000588 sqlite3VdbeResolveLabel(v, addrDone);
000589 }
000590
000591 #if SQLITE_MAX_EXPR_DEPTH>0
000592 /*
000593 ** Check that argument nHeight is less than or equal to the maximum
000594 ** expression depth allowed. If it is not, leave an error message in
000595 ** pParse.
000596 */
000597 int sqlite3ExprCheckHeight(Parse *pParse, int nHeight){
000598 int rc = SQLITE_OK;
000599 int mxHeight = pParse->db->aLimit[SQLITE_LIMIT_EXPR_DEPTH];
000600 if( nHeight>mxHeight ){
000601 sqlite3ErrorMsg(pParse,
000602 "Expression tree is too large (maximum depth %d)", mxHeight
000603 );
000604 rc = SQLITE_ERROR;
000605 }
000606 return rc;
000607 }
000608
000609 /* The following three functions, heightOfExpr(), heightOfExprList()
000610 ** and heightOfSelect(), are used to determine the maximum height
000611 ** of any expression tree referenced by the structure passed as the
000612 ** first argument.
000613 **
000614 ** If this maximum height is greater than the current value pointed
000615 ** to by pnHeight, the second parameter, then set *pnHeight to that
000616 ** value.
000617 */
000618 static void heightOfExpr(Expr *p, int *pnHeight){
000619 if( p ){
000620 if( p->nHeight>*pnHeight ){
000621 *pnHeight = p->nHeight;
000622 }
000623 }
000624 }
000625 static void heightOfExprList(ExprList *p, int *pnHeight){
000626 if( p ){
000627 int i;
000628 for(i=0; i<p->nExpr; i++){
000629 heightOfExpr(p->a[i].pExpr, pnHeight);
000630 }
000631 }
000632 }
000633 static void heightOfSelect(Select *p, int *pnHeight){
000634 if( p ){
000635 heightOfExpr(p->pWhere, pnHeight);
000636 heightOfExpr(p->pHaving, pnHeight);
000637 heightOfExpr(p->pLimit, pnHeight);
000638 heightOfExpr(p->pOffset, pnHeight);
000639 heightOfExprList(p->pEList, pnHeight);
000640 heightOfExprList(p->pGroupBy, pnHeight);
000641 heightOfExprList(p->pOrderBy, pnHeight);
000642 heightOfSelect(p->pPrior, pnHeight);
000643 }
000644 }
000645
000646 /*
000647 ** Set the Expr.nHeight variable in the structure passed as an
000648 ** argument. An expression with no children, Expr.pList or
000649 ** Expr.pSelect member has a height of 1. Any other expression
000650 ** has a height equal to the maximum height of any other
000651 ** referenced Expr plus one.
000652 **
000653 ** Also propagate EP_Propagate flags up from Expr.x.pList to Expr.flags,
000654 ** if appropriate.
000655 */
000656 static void exprSetHeight(Expr *p){
000657 int nHeight = 0;
000658 heightOfExpr(p->pLeft, &nHeight);
000659 heightOfExpr(p->pRight, &nHeight);
000660 if( ExprHasProperty(p, EP_xIsSelect) ){
000661 heightOfSelect(p->x.pSelect, &nHeight);
000662 }else if( p->x.pList ){
000663 heightOfExprList(p->x.pList, &nHeight);
000664 p->flags |= EP_Propagate & sqlite3ExprListFlags(p->x.pList);
000665 }
000666 p->nHeight = nHeight + 1;
000667 }
000668
000669 /*
000670 ** Set the Expr.nHeight variable using the exprSetHeight() function. If
000671 ** the height is greater than the maximum allowed expression depth,
000672 ** leave an error in pParse.
000673 **
000674 ** Also propagate all EP_Propagate flags from the Expr.x.pList into
000675 ** Expr.flags.
000676 */
000677 void sqlite3ExprSetHeightAndFlags(Parse *pParse, Expr *p){
000678 if( pParse->nErr ) return;
000679 exprSetHeight(p);
000680 sqlite3ExprCheckHeight(pParse, p->nHeight);
000681 }
000682
000683 /*
000684 ** Return the maximum height of any expression tree referenced
000685 ** by the select statement passed as an argument.
000686 */
000687 int sqlite3SelectExprHeight(Select *p){
000688 int nHeight = 0;
000689 heightOfSelect(p, &nHeight);
000690 return nHeight;
000691 }
000692 #else /* ABOVE: Height enforcement enabled. BELOW: Height enforcement off */
000693 /*
000694 ** Propagate all EP_Propagate flags from the Expr.x.pList into
000695 ** Expr.flags.
000696 */
000697 void sqlite3ExprSetHeightAndFlags(Parse *pParse, Expr *p){
000698 if( p && p->x.pList && !ExprHasProperty(p, EP_xIsSelect) ){
000699 p->flags |= EP_Propagate & sqlite3ExprListFlags(p->x.pList);
000700 }
000701 }
000702 #define exprSetHeight(y)
000703 #endif /* SQLITE_MAX_EXPR_DEPTH>0 */
000704
000705 /*
000706 ** This routine is the core allocator for Expr nodes.
000707 **
000708 ** Construct a new expression node and return a pointer to it. Memory
000709 ** for this node and for the pToken argument is a single allocation
000710 ** obtained from sqlite3DbMalloc(). The calling function
000711 ** is responsible for making sure the node eventually gets freed.
000712 **
000713 ** If dequote is true, then the token (if it exists) is dequoted.
000714 ** If dequote is false, no dequoting is performed. The deQuote
000715 ** parameter is ignored if pToken is NULL or if the token does not
000716 ** appear to be quoted. If the quotes were of the form "..." (double-quotes)
000717 ** then the EP_DblQuoted flag is set on the expression node.
000718 **
000719 ** Special case: If op==TK_INTEGER and pToken points to a string that
000720 ** can be translated into a 32-bit integer, then the token is not
000721 ** stored in u.zToken. Instead, the integer values is written
000722 ** into u.iValue and the EP_IntValue flag is set. No extra storage
000723 ** is allocated to hold the integer text and the dequote flag is ignored.
000724 */
000725 Expr *sqlite3ExprAlloc(
000726 sqlite3 *db, /* Handle for sqlite3DbMallocRawNN() */
000727 int op, /* Expression opcode */
000728 const Token *pToken, /* Token argument. Might be NULL */
000729 int dequote /* True to dequote */
000730 ){
000731 Expr *pNew;
000732 int nExtra = 0;
000733 int iValue = 0;
000734
000735 assert( db!=0 );
000736 if( pToken ){
000737 if( op!=TK_INTEGER || pToken->z==0
000738 || sqlite3GetInt32(pToken->z, &iValue)==0 ){
000739 nExtra = pToken->n+1;
000740 assert( iValue>=0 );
000741 }
000742 }
000743 pNew = sqlite3DbMallocRawNN(db, sizeof(Expr)+nExtra);
000744 if( pNew ){
000745 memset(pNew, 0, sizeof(Expr));
000746 pNew->op = (u8)op;
000747 pNew->iAgg = -1;
000748 if( pToken ){
000749 if( nExtra==0 ){
000750 pNew->flags |= EP_IntValue;
000751 pNew->u.iValue = iValue;
000752 }else{
000753 pNew->u.zToken = (char*)&pNew[1];
000754 assert( pToken->z!=0 || pToken->n==0 );
000755 if( pToken->n ) memcpy(pNew->u.zToken, pToken->z, pToken->n);
000756 pNew->u.zToken[pToken->n] = 0;
000757 if( dequote && sqlite3Isquote(pNew->u.zToken[0]) ){
000758 if( pNew->u.zToken[0]=='"' ) pNew->flags |= EP_DblQuoted;
000759 sqlite3Dequote(pNew->u.zToken);
000760 }
000761 }
000762 }
000763 #if SQLITE_MAX_EXPR_DEPTH>0
000764 pNew->nHeight = 1;
000765 #endif
000766 }
000767 return pNew;
000768 }
000769
000770 /*
000771 ** Allocate a new expression node from a zero-terminated token that has
000772 ** already been dequoted.
000773 */
000774 Expr *sqlite3Expr(
000775 sqlite3 *db, /* Handle for sqlite3DbMallocZero() (may be null) */
000776 int op, /* Expression opcode */
000777 const char *zToken /* Token argument. Might be NULL */
000778 ){
000779 Token x;
000780 x.z = zToken;
000781 x.n = zToken ? sqlite3Strlen30(zToken) : 0;
000782 return sqlite3ExprAlloc(db, op, &x, 0);
000783 }
000784
000785 /*
000786 ** Attach subtrees pLeft and pRight to the Expr node pRoot.
000787 **
000788 ** If pRoot==NULL that means that a memory allocation error has occurred.
000789 ** In that case, delete the subtrees pLeft and pRight.
000790 */
000791 void sqlite3ExprAttachSubtrees(
000792 sqlite3 *db,
000793 Expr *pRoot,
000794 Expr *pLeft,
000795 Expr *pRight
000796 ){
000797 if( pRoot==0 ){
000798 assert( db->mallocFailed );
000799 sqlite3ExprDelete(db, pLeft);
000800 sqlite3ExprDelete(db, pRight);
000801 }else{
000802 if( pRight ){
000803 pRoot->pRight = pRight;
000804 pRoot->flags |= EP_Propagate & pRight->flags;
000805 }
000806 if( pLeft ){
000807 pRoot->pLeft = pLeft;
000808 pRoot->flags |= EP_Propagate & pLeft->flags;
000809 }
000810 exprSetHeight(pRoot);
000811 }
000812 }
000813
000814 /*
000815 ** Allocate an Expr node which joins as many as two subtrees.
000816 **
000817 ** One or both of the subtrees can be NULL. Return a pointer to the new
000818 ** Expr node. Or, if an OOM error occurs, set pParse->db->mallocFailed,
000819 ** free the subtrees and return NULL.
000820 */
000821 Expr *sqlite3PExpr(
000822 Parse *pParse, /* Parsing context */
000823 int op, /* Expression opcode */
000824 Expr *pLeft, /* Left operand */
000825 Expr *pRight /* Right operand */
000826 ){
000827 Expr *p;
000828 if( op==TK_AND && pParse->nErr==0 ){
000829 /* Take advantage of short-circuit false optimization for AND */
000830 p = sqlite3ExprAnd(pParse->db, pLeft, pRight);
000831 }else{
000832 p = sqlite3DbMallocRawNN(pParse->db, sizeof(Expr));
000833 if( p ){
000834 memset(p, 0, sizeof(Expr));
000835 p->op = op & TKFLG_MASK;
000836 p->iAgg = -1;
000837 }
000838 sqlite3ExprAttachSubtrees(pParse->db, p, pLeft, pRight);
000839 }
000840 if( p ) {
000841 sqlite3ExprCheckHeight(pParse, p->nHeight);
000842 }
000843 return p;
000844 }
000845
000846 /*
000847 ** Add pSelect to the Expr.x.pSelect field. Or, if pExpr is NULL (due
000848 ** do a memory allocation failure) then delete the pSelect object.
000849 */
000850 void sqlite3PExprAddSelect(Parse *pParse, Expr *pExpr, Select *pSelect){
000851 if( pExpr ){
000852 pExpr->x.pSelect = pSelect;
000853 ExprSetProperty(pExpr, EP_xIsSelect|EP_Subquery);
000854 sqlite3ExprSetHeightAndFlags(pParse, pExpr);
000855 }else{
000856 assert( pParse->db->mallocFailed );
000857 sqlite3SelectDelete(pParse->db, pSelect);
000858 }
000859 }
000860
000861
000862 /*
000863 ** If the expression is always either TRUE or FALSE (respectively),
000864 ** then return 1. If one cannot determine the truth value of the
000865 ** expression at compile-time return 0.
000866 **
000867 ** This is an optimization. If is OK to return 0 here even if
000868 ** the expression really is always false or false (a false negative).
000869 ** But it is a bug to return 1 if the expression might have different
000870 ** boolean values in different circumstances (a false positive.)
000871 **
000872 ** Note that if the expression is part of conditional for a
000873 ** LEFT JOIN, then we cannot determine at compile-time whether or not
000874 ** is it true or false, so always return 0.
000875 */
000876 static int exprAlwaysTrue(Expr *p){
000877 int v = 0;
000878 if( ExprHasProperty(p, EP_FromJoin) ) return 0;
000879 if( !sqlite3ExprIsInteger(p, &v) ) return 0;
000880 return v!=0;
000881 }
000882 static int exprAlwaysFalse(Expr *p){
000883 int v = 0;
000884 if( ExprHasProperty(p, EP_FromJoin) ) return 0;
000885 if( !sqlite3ExprIsInteger(p, &v) ) return 0;
000886 return v==0;
000887 }
000888
000889 /*
000890 ** Join two expressions using an AND operator. If either expression is
000891 ** NULL, then just return the other expression.
000892 **
000893 ** If one side or the other of the AND is known to be false, then instead
000894 ** of returning an AND expression, just return a constant expression with
000895 ** a value of false.
000896 */
000897 Expr *sqlite3ExprAnd(sqlite3 *db, Expr *pLeft, Expr *pRight){
000898 if( pLeft==0 ){
000899 return pRight;
000900 }else if( pRight==0 ){
000901 return pLeft;
000902 }else if( exprAlwaysFalse(pLeft) || exprAlwaysFalse(pRight) ){
000903 sqlite3ExprDelete(db, pLeft);
000904 sqlite3ExprDelete(db, pRight);
000905 return sqlite3ExprAlloc(db, TK_INTEGER, &sqlite3IntTokens[0], 0);
000906 }else{
000907 Expr *pNew = sqlite3ExprAlloc(db, TK_AND, 0, 0);
000908 sqlite3ExprAttachSubtrees(db, pNew, pLeft, pRight);
000909 return pNew;
000910 }
000911 }
000912
000913 /*
000914 ** Construct a new expression node for a function with multiple
000915 ** arguments.
000916 */
000917 Expr *sqlite3ExprFunction(Parse *pParse, ExprList *pList, Token *pToken){
000918 Expr *pNew;
000919 sqlite3 *db = pParse->db;
000920 assert( pToken );
000921 pNew = sqlite3ExprAlloc(db, TK_FUNCTION, pToken, 1);
000922 if( pNew==0 ){
000923 sqlite3ExprListDelete(db, pList); /* Avoid memory leak when malloc fails */
000924 return 0;
000925 }
000926 pNew->x.pList = pList;
000927 assert( !ExprHasProperty(pNew, EP_xIsSelect) );
000928 sqlite3ExprSetHeightAndFlags(pParse, pNew);
000929 return pNew;
000930 }
000931
000932 /*
000933 ** Assign a variable number to an expression that encodes a wildcard
000934 ** in the original SQL statement.
000935 **
000936 ** Wildcards consisting of a single "?" are assigned the next sequential
000937 ** variable number.
000938 **
000939 ** Wildcards of the form "?nnn" are assigned the number "nnn". We make
000940 ** sure "nnn" is not too big to avoid a denial of service attack when
000941 ** the SQL statement comes from an external source.
000942 **
000943 ** Wildcards of the form ":aaa", "@aaa", or "$aaa" are assigned the same number
000944 ** as the previous instance of the same wildcard. Or if this is the first
000945 ** instance of the wildcard, the next sequential variable number is
000946 ** assigned.
000947 */
000948 void sqlite3ExprAssignVarNumber(Parse *pParse, Expr *pExpr, u32 n){
000949 sqlite3 *db = pParse->db;
000950 const char *z;
000951 ynVar x;
000952
000953 if( pExpr==0 ) return;
000954 assert( !ExprHasProperty(pExpr, EP_IntValue|EP_Reduced|EP_TokenOnly) );
000955 z = pExpr->u.zToken;
000956 assert( z!=0 );
000957 assert( z[0]!=0 );
000958 assert( n==sqlite3Strlen30(z) );
000959 if( z[1]==0 ){
000960 /* Wildcard of the form "?". Assign the next variable number */
000961 assert( z[0]=='?' );
000962 x = (ynVar)(++pParse->nVar);
000963 }else{
000964 int doAdd = 0;
000965 if( z[0]=='?' ){
000966 /* Wildcard of the form "?nnn". Convert "nnn" to an integer and
000967 ** use it as the variable number */
000968 i64 i;
000969 int bOk = 0==sqlite3Atoi64(&z[1], &i, n-1, SQLITE_UTF8);
000970 x = (ynVar)i;
000971 testcase( i==0 );
000972 testcase( i==1 );
000973 testcase( i==db->aLimit[SQLITE_LIMIT_VARIABLE_NUMBER]-1 );
000974 testcase( i==db->aLimit[SQLITE_LIMIT_VARIABLE_NUMBER] );
000975 if( bOk==0 || i<1 || i>db->aLimit[SQLITE_LIMIT_VARIABLE_NUMBER] ){
000976 sqlite3ErrorMsg(pParse, "variable number must be between ?1 and ?%d",
000977 db->aLimit[SQLITE_LIMIT_VARIABLE_NUMBER]);
000978 return;
000979 }
000980 if( x>pParse->nVar ){
000981 pParse->nVar = (int)x;
000982 doAdd = 1;
000983 }else if( sqlite3VListNumToName(pParse->pVList, x)==0 ){
000984 doAdd = 1;
000985 }
000986 }else{
000987 /* Wildcards like ":aaa", "$aaa" or "@aaa". Reuse the same variable
000988 ** number as the prior appearance of the same name, or if the name
000989 ** has never appeared before, reuse the same variable number
000990 */
000991 x = (ynVar)sqlite3VListNameToNum(pParse->pVList, z, n);
000992 if( x==0 ){
000993 x = (ynVar)(++pParse->nVar);
000994 doAdd = 1;
000995 }
000996 }
000997 if( doAdd ){
000998 pParse->pVList = sqlite3VListAdd(db, pParse->pVList, z, n, x);
000999 }
001000 }
001001 pExpr->iColumn = x;
001002 if( x>db->aLimit[SQLITE_LIMIT_VARIABLE_NUMBER] ){
001003 sqlite3ErrorMsg(pParse, "too many SQL variables");
001004 }
001005 }
001006
001007 /*
001008 ** Recursively delete an expression tree.
001009 */
001010 static SQLITE_NOINLINE void sqlite3ExprDeleteNN(sqlite3 *db, Expr *p){
001011 assert( p!=0 );
001012 /* Sanity check: Assert that the IntValue is non-negative if it exists */
001013 assert( !ExprHasProperty(p, EP_IntValue) || p->u.iValue>=0 );
001014 #ifdef SQLITE_DEBUG
001015 if( ExprHasProperty(p, EP_Leaf) && !ExprHasProperty(p, EP_TokenOnly) ){
001016 assert( p->pLeft==0 );
001017 assert( p->pRight==0 );
001018 assert( p->x.pSelect==0 );
001019 }
001020 #endif
001021 if( !ExprHasProperty(p, (EP_TokenOnly|EP_Leaf)) ){
001022 /* The Expr.x union is never used at the same time as Expr.pRight */
001023 assert( p->x.pList==0 || p->pRight==0 );
001024 if( p->pLeft && p->op!=TK_SELECT_COLUMN ) sqlite3ExprDeleteNN(db, p->pLeft);
001025 sqlite3ExprDelete(db, p->pRight);
001026 if( ExprHasProperty(p, EP_xIsSelect) ){
001027 sqlite3SelectDelete(db, p->x.pSelect);
001028 }else{
001029 sqlite3ExprListDelete(db, p->x.pList);
001030 }
001031 }
001032 if( ExprHasProperty(p, EP_MemToken) ) sqlite3DbFree(db, p->u.zToken);
001033 if( !ExprHasProperty(p, EP_Static) ){
001034 sqlite3DbFree(db, p);
001035 }
001036 }
001037 void sqlite3ExprDelete(sqlite3 *db, Expr *p){
001038 if( p ) sqlite3ExprDeleteNN(db, p);
001039 }
001040
001041 /*
001042 ** Return the number of bytes allocated for the expression structure
001043 ** passed as the first argument. This is always one of EXPR_FULLSIZE,
001044 ** EXPR_REDUCEDSIZE or EXPR_TOKENONLYSIZE.
001045 */
001046 static int exprStructSize(Expr *p){
001047 if( ExprHasProperty(p, EP_TokenOnly) ) return EXPR_TOKENONLYSIZE;
001048 if( ExprHasProperty(p, EP_Reduced) ) return EXPR_REDUCEDSIZE;
001049 return EXPR_FULLSIZE;
001050 }
001051
001052 /*
001053 ** The dupedExpr*Size() routines each return the number of bytes required
001054 ** to store a copy of an expression or expression tree. They differ in
001055 ** how much of the tree is measured.
001056 **
001057 ** dupedExprStructSize() Size of only the Expr structure
001058 ** dupedExprNodeSize() Size of Expr + space for token
001059 ** dupedExprSize() Expr + token + subtree components
001060 **
001061 ***************************************************************************
001062 **
001063 ** The dupedExprStructSize() function returns two values OR-ed together:
001064 ** (1) the space required for a copy of the Expr structure only and
001065 ** (2) the EP_xxx flags that indicate what the structure size should be.
001066 ** The return values is always one of:
001067 **
001068 ** EXPR_FULLSIZE
001069 ** EXPR_REDUCEDSIZE | EP_Reduced
001070 ** EXPR_TOKENONLYSIZE | EP_TokenOnly
001071 **
001072 ** The size of the structure can be found by masking the return value
001073 ** of this routine with 0xfff. The flags can be found by masking the
001074 ** return value with EP_Reduced|EP_TokenOnly.
001075 **
001076 ** Note that with flags==EXPRDUP_REDUCE, this routines works on full-size
001077 ** (unreduced) Expr objects as they or originally constructed by the parser.
001078 ** During expression analysis, extra information is computed and moved into
001079 ** later parts of teh Expr object and that extra information might get chopped
001080 ** off if the expression is reduced. Note also that it does not work to
001081 ** make an EXPRDUP_REDUCE copy of a reduced expression. It is only legal
001082 ** to reduce a pristine expression tree from the parser. The implementation
001083 ** of dupedExprStructSize() contain multiple assert() statements that attempt
001084 ** to enforce this constraint.
001085 */
001086 static int dupedExprStructSize(Expr *p, int flags){
001087 int nSize;
001088 assert( flags==EXPRDUP_REDUCE || flags==0 ); /* Only one flag value allowed */
001089 assert( EXPR_FULLSIZE<=0xfff );
001090 assert( (0xfff & (EP_Reduced|EP_TokenOnly))==0 );
001091 if( 0==flags ){
001092 nSize = EXPR_FULLSIZE;
001093 }else{
001094 assert( !ExprHasProperty(p, EP_TokenOnly|EP_Reduced) );
001095 assert( !ExprHasProperty(p, EP_FromJoin) );
001096 assert( !ExprHasProperty(p, EP_MemToken) );
001097 assert( !ExprHasProperty(p, EP_NoReduce) );
001098 if( p->pLeft || p->x.pList ){
001099 nSize = EXPR_REDUCEDSIZE | EP_Reduced;
001100 }else{
001101 assert( p->pRight==0 );
001102 nSize = EXPR_TOKENONLYSIZE | EP_TokenOnly;
001103 }
001104 }
001105 return nSize;
001106 }
001107
001108 /*
001109 ** This function returns the space in bytes required to store the copy
001110 ** of the Expr structure and a copy of the Expr.u.zToken string (if that
001111 ** string is defined.)
001112 */
001113 static int dupedExprNodeSize(Expr *p, int flags){
001114 int nByte = dupedExprStructSize(p, flags) & 0xfff;
001115 if( !ExprHasProperty(p, EP_IntValue) && p->u.zToken ){
001116 nByte += sqlite3Strlen30(p->u.zToken)+1;
001117 }
001118 return ROUND8(nByte);
001119 }
001120
001121 /*
001122 ** Return the number of bytes required to create a duplicate of the
001123 ** expression passed as the first argument. The second argument is a
001124 ** mask containing EXPRDUP_XXX flags.
001125 **
001126 ** The value returned includes space to create a copy of the Expr struct
001127 ** itself and the buffer referred to by Expr.u.zToken, if any.
001128 **
001129 ** If the EXPRDUP_REDUCE flag is set, then the return value includes
001130 ** space to duplicate all Expr nodes in the tree formed by Expr.pLeft
001131 ** and Expr.pRight variables (but not for any structures pointed to or
001132 ** descended from the Expr.x.pList or Expr.x.pSelect variables).
001133 */
001134 static int dupedExprSize(Expr *p, int flags){
001135 int nByte = 0;
001136 if( p ){
001137 nByte = dupedExprNodeSize(p, flags);
001138 if( flags&EXPRDUP_REDUCE ){
001139 nByte += dupedExprSize(p->pLeft, flags) + dupedExprSize(p->pRight, flags);
001140 }
001141 }
001142 return nByte;
001143 }
001144
001145 /*
001146 ** This function is similar to sqlite3ExprDup(), except that if pzBuffer
001147 ** is not NULL then *pzBuffer is assumed to point to a buffer large enough
001148 ** to store the copy of expression p, the copies of p->u.zToken
001149 ** (if applicable), and the copies of the p->pLeft and p->pRight expressions,
001150 ** if any. Before returning, *pzBuffer is set to the first byte past the
001151 ** portion of the buffer copied into by this function.
001152 */
001153 static Expr *exprDup(sqlite3 *db, Expr *p, int dupFlags, u8 **pzBuffer){
001154 Expr *pNew; /* Value to return */
001155 u8 *zAlloc; /* Memory space from which to build Expr object */
001156 u32 staticFlag; /* EP_Static if space not obtained from malloc */
001157
001158 assert( db!=0 );
001159 assert( p );
001160 assert( dupFlags==0 || dupFlags==EXPRDUP_REDUCE );
001161 assert( pzBuffer==0 || dupFlags==EXPRDUP_REDUCE );
001162
001163 /* Figure out where to write the new Expr structure. */
001164 if( pzBuffer ){
001165 zAlloc = *pzBuffer;
001166 staticFlag = EP_Static;
001167 }else{
001168 zAlloc = sqlite3DbMallocRawNN(db, dupedExprSize(p, dupFlags));
001169 staticFlag = 0;
001170 }
001171 pNew = (Expr *)zAlloc;
001172
001173 if( pNew ){
001174 /* Set nNewSize to the size allocated for the structure pointed to
001175 ** by pNew. This is either EXPR_FULLSIZE, EXPR_REDUCEDSIZE or
001176 ** EXPR_TOKENONLYSIZE. nToken is set to the number of bytes consumed
001177 ** by the copy of the p->u.zToken string (if any).
001178 */
001179 const unsigned nStructSize = dupedExprStructSize(p, dupFlags);
001180 const int nNewSize = nStructSize & 0xfff;
001181 int nToken;
001182 if( !ExprHasProperty(p, EP_IntValue) && p->u.zToken ){
001183 nToken = sqlite3Strlen30(p->u.zToken) + 1;
001184 }else{
001185 nToken = 0;
001186 }
001187 if( dupFlags ){
001188 assert( ExprHasProperty(p, EP_Reduced)==0 );
001189 memcpy(zAlloc, p, nNewSize);
001190 }else{
001191 u32 nSize = (u32)exprStructSize(p);
001192 memcpy(zAlloc, p, nSize);
001193 if( nSize<EXPR_FULLSIZE ){
001194 memset(&zAlloc[nSize], 0, EXPR_FULLSIZE-nSize);
001195 }
001196 }
001197
001198 /* Set the EP_Reduced, EP_TokenOnly, and EP_Static flags appropriately. */
001199 pNew->flags &= ~(EP_Reduced|EP_TokenOnly|EP_Static|EP_MemToken);
001200 pNew->flags |= nStructSize & (EP_Reduced|EP_TokenOnly);
001201 pNew->flags |= staticFlag;
001202
001203 /* Copy the p->u.zToken string, if any. */
001204 if( nToken ){
001205 char *zToken = pNew->u.zToken = (char*)&zAlloc[nNewSize];
001206 memcpy(zToken, p->u.zToken, nToken);
001207 }
001208
001209 if( 0==((p->flags|pNew->flags) & (EP_TokenOnly|EP_Leaf)) ){
001210 /* Fill in the pNew->x.pSelect or pNew->x.pList member. */
001211 if( ExprHasProperty(p, EP_xIsSelect) ){
001212 pNew->x.pSelect = sqlite3SelectDup(db, p->x.pSelect, dupFlags);
001213 }else{
001214 pNew->x.pList = sqlite3ExprListDup(db, p->x.pList, dupFlags);
001215 }
001216 }
001217
001218 /* Fill in pNew->pLeft and pNew->pRight. */
001219 if( ExprHasProperty(pNew, EP_Reduced|EP_TokenOnly) ){
001220 zAlloc += dupedExprNodeSize(p, dupFlags);
001221 if( !ExprHasProperty(pNew, EP_TokenOnly|EP_Leaf) ){
001222 pNew->pLeft = p->pLeft ?
001223 exprDup(db, p->pLeft, EXPRDUP_REDUCE, &zAlloc) : 0;
001224 pNew->pRight = p->pRight ?
001225 exprDup(db, p->pRight, EXPRDUP_REDUCE, &zAlloc) : 0;
001226 }
001227 if( pzBuffer ){
001228 *pzBuffer = zAlloc;
001229 }
001230 }else{
001231 if( !ExprHasProperty(p, EP_TokenOnly|EP_Leaf) ){
001232 if( pNew->op==TK_SELECT_COLUMN ){
001233 pNew->pLeft = p->pLeft;
001234 }else{
001235 pNew->pLeft = sqlite3ExprDup(db, p->pLeft, 0);
001236 }
001237 pNew->pRight = sqlite3ExprDup(db, p->pRight, 0);
001238 }
001239 }
001240 }
001241 return pNew;
001242 }
001243
001244 /*
001245 ** Create and return a deep copy of the object passed as the second
001246 ** argument. If an OOM condition is encountered, NULL is returned
001247 ** and the db->mallocFailed flag set.
001248 */
001249 #ifndef SQLITE_OMIT_CTE
001250 static With *withDup(sqlite3 *db, With *p){
001251 With *pRet = 0;
001252 if( p ){
001253 int nByte = sizeof(*p) + sizeof(p->a[0]) * (p->nCte-1);
001254 pRet = sqlite3DbMallocZero(db, nByte);
001255 if( pRet ){
001256 int i;
001257 pRet->nCte = p->nCte;
001258 for(i=0; i<p->nCte; i++){
001259 pRet->a[i].pSelect = sqlite3SelectDup(db, p->a[i].pSelect, 0);
001260 pRet->a[i].pCols = sqlite3ExprListDup(db, p->a[i].pCols, 0);
001261 pRet->a[i].zName = sqlite3DbStrDup(db, p->a[i].zName);
001262 }
001263 }
001264 }
001265 return pRet;
001266 }
001267 #else
001268 # define withDup(x,y) 0
001269 #endif
001270
001271 /*
001272 ** The following group of routines make deep copies of expressions,
001273 ** expression lists, ID lists, and select statements. The copies can
001274 ** be deleted (by being passed to their respective ...Delete() routines)
001275 ** without effecting the originals.
001276 **
001277 ** The expression list, ID, and source lists return by sqlite3ExprListDup(),
001278 ** sqlite3IdListDup(), and sqlite3SrcListDup() can not be further expanded
001279 ** by subsequent calls to sqlite*ListAppend() routines.
001280 **
001281 ** Any tables that the SrcList might point to are not duplicated.
001282 **
001283 ** The flags parameter contains a combination of the EXPRDUP_XXX flags.
001284 ** If the EXPRDUP_REDUCE flag is set, then the structure returned is a
001285 ** truncated version of the usual Expr structure that will be stored as
001286 ** part of the in-memory representation of the database schema.
001287 */
001288 Expr *sqlite3ExprDup(sqlite3 *db, Expr *p, int flags){
001289 assert( flags==0 || flags==EXPRDUP_REDUCE );
001290 return p ? exprDup(db, p, flags, 0) : 0;
001291 }
001292 ExprList *sqlite3ExprListDup(sqlite3 *db, ExprList *p, int flags){
001293 ExprList *pNew;
001294 struct ExprList_item *pItem, *pOldItem;
001295 int i;
001296 assert( db!=0 );
001297 if( p==0 ) return 0;
001298 pNew = sqlite3DbMallocRawNN(db, sizeof(*pNew) );
001299 if( pNew==0 ) return 0;
001300 pNew->nExpr = i = p->nExpr;
001301 if( (flags & EXPRDUP_REDUCE)==0 ) for(i=1; i<p->nExpr; i+=i){}
001302 pNew->a = pItem = sqlite3DbMallocRawNN(db, i*sizeof(p->a[0]) );
001303 if( pItem==0 ){
001304 sqlite3DbFree(db, pNew);
001305 return 0;
001306 }
001307 pOldItem = p->a;
001308 for(i=0; i<p->nExpr; i++, pItem++, pOldItem++){
001309 Expr *pOldExpr = pOldItem->pExpr;
001310 pItem->pExpr = sqlite3ExprDup(db, pOldExpr, flags);
001311 pItem->zName = sqlite3DbStrDup(db, pOldItem->zName);
001312 pItem->zSpan = sqlite3DbStrDup(db, pOldItem->zSpan);
001313 pItem->sortOrder = pOldItem->sortOrder;
001314 pItem->done = 0;
001315 pItem->bSpanIsTab = pOldItem->bSpanIsTab;
001316 pItem->u = pOldItem->u;
001317 }
001318 return pNew;
001319 }
001320
001321 /*
001322 ** If cursors, triggers, views and subqueries are all omitted from
001323 ** the build, then none of the following routines, except for
001324 ** sqlite3SelectDup(), can be called. sqlite3SelectDup() is sometimes
001325 ** called with a NULL argument.
001326 */
001327 #if !defined(SQLITE_OMIT_VIEW) || !defined(SQLITE_OMIT_TRIGGER) \
001328 || !defined(SQLITE_OMIT_SUBQUERY)
001329 SrcList *sqlite3SrcListDup(sqlite3 *db, SrcList *p, int flags){
001330 SrcList *pNew;
001331 int i;
001332 int nByte;
001333 assert( db!=0 );
001334 if( p==0 ) return 0;
001335 nByte = sizeof(*p) + (p->nSrc>0 ? sizeof(p->a[0]) * (p->nSrc-1) : 0);
001336 pNew = sqlite3DbMallocRawNN(db, nByte );
001337 if( pNew==0 ) return 0;
001338 pNew->nSrc = pNew->nAlloc = p->nSrc;
001339 for(i=0; i<p->nSrc; i++){
001340 struct SrcList_item *pNewItem = &pNew->a[i];
001341 struct SrcList_item *pOldItem = &p->a[i];
001342 Table *pTab;
001343 pNewItem->pSchema = pOldItem->pSchema;
001344 pNewItem->zDatabase = sqlite3DbStrDup(db, pOldItem->zDatabase);
001345 pNewItem->zName = sqlite3DbStrDup(db, pOldItem->zName);
001346 pNewItem->zAlias = sqlite3DbStrDup(db, pOldItem->zAlias);
001347 pNewItem->fg = pOldItem->fg;
001348 pNewItem->iCursor = pOldItem->iCursor;
001349 pNewItem->addrFillSub = pOldItem->addrFillSub;
001350 pNewItem->regReturn = pOldItem->regReturn;
001351 if( pNewItem->fg.isIndexedBy ){
001352 pNewItem->u1.zIndexedBy = sqlite3DbStrDup(db, pOldItem->u1.zIndexedBy);
001353 }
001354 pNewItem->pIBIndex = pOldItem->pIBIndex;
001355 if( pNewItem->fg.isTabFunc ){
001356 pNewItem->u1.pFuncArg =
001357 sqlite3ExprListDup(db, pOldItem->u1.pFuncArg, flags);
001358 }
001359 pTab = pNewItem->pTab = pOldItem->pTab;
001360 if( pTab ){
001361 pTab->nTabRef++;
001362 }
001363 pNewItem->pSelect = sqlite3SelectDup(db, pOldItem->pSelect, flags);
001364 pNewItem->pOn = sqlite3ExprDup(db, pOldItem->pOn, flags);
001365 pNewItem->pUsing = sqlite3IdListDup(db, pOldItem->pUsing);
001366 pNewItem->colUsed = pOldItem->colUsed;
001367 }
001368 return pNew;
001369 }
001370 IdList *sqlite3IdListDup(sqlite3 *db, IdList *p){
001371 IdList *pNew;
001372 int i;
001373 assert( db!=0 );
001374 if( p==0 ) return 0;
001375 pNew = sqlite3DbMallocRawNN(db, sizeof(*pNew) );
001376 if( pNew==0 ) return 0;
001377 pNew->nId = p->nId;
001378 pNew->a = sqlite3DbMallocRawNN(db, p->nId*sizeof(p->a[0]) );
001379 if( pNew->a==0 ){
001380 sqlite3DbFree(db, pNew);
001381 return 0;
001382 }
001383 /* Note that because the size of the allocation for p->a[] is not
001384 ** necessarily a power of two, sqlite3IdListAppend() may not be called
001385 ** on the duplicate created by this function. */
001386 for(i=0; i<p->nId; i++){
001387 struct IdList_item *pNewItem = &pNew->a[i];
001388 struct IdList_item *pOldItem = &p->a[i];
001389 pNewItem->zName = sqlite3DbStrDup(db, pOldItem->zName);
001390 pNewItem->idx = pOldItem->idx;
001391 }
001392 return pNew;
001393 }
001394 Select *sqlite3SelectDup(sqlite3 *db, Select *p, int flags){
001395 Select *pNew, *pPrior;
001396 assert( db!=0 );
001397 if( p==0 ) return 0;
001398 pNew = sqlite3DbMallocRawNN(db, sizeof(*p) );
001399 if( pNew==0 ) return 0;
001400 pNew->pEList = sqlite3ExprListDup(db, p->pEList, flags);
001401 pNew->pSrc = sqlite3SrcListDup(db, p->pSrc, flags);
001402 pNew->pWhere = sqlite3ExprDup(db, p->pWhere, flags);
001403 pNew->pGroupBy = sqlite3ExprListDup(db, p->pGroupBy, flags);
001404 pNew->pHaving = sqlite3ExprDup(db, p->pHaving, flags);
001405 pNew->pOrderBy = sqlite3ExprListDup(db, p->pOrderBy, flags);
001406 pNew->op = p->op;
001407 pNew->pPrior = pPrior = sqlite3SelectDup(db, p->pPrior, flags);
001408 if( pPrior ) pPrior->pNext = pNew;
001409 pNew->pNext = 0;
001410 pNew->pLimit = sqlite3ExprDup(db, p->pLimit, flags);
001411 pNew->pOffset = sqlite3ExprDup(db, p->pOffset, flags);
001412 pNew->iLimit = 0;
001413 pNew->iOffset = 0;
001414 pNew->selFlags = p->selFlags & ~SF_UsesEphemeral;
001415 pNew->addrOpenEphm[0] = -1;
001416 pNew->addrOpenEphm[1] = -1;
001417 pNew->nSelectRow = p->nSelectRow;
001418 pNew->pWith = withDup(db, p->pWith);
001419 sqlite3SelectSetName(pNew, p->zSelName);
001420 return pNew;
001421 }
001422 #else
001423 Select *sqlite3SelectDup(sqlite3 *db, Select *p, int flags){
001424 assert( p==0 );
001425 return 0;
001426 }
001427 #endif
001428
001429
001430 /*
001431 ** Add a new element to the end of an expression list. If pList is
001432 ** initially NULL, then create a new expression list.
001433 **
001434 ** If a memory allocation error occurs, the entire list is freed and
001435 ** NULL is returned. If non-NULL is returned, then it is guaranteed
001436 ** that the new entry was successfully appended.
001437 */
001438 ExprList *sqlite3ExprListAppend(
001439 Parse *pParse, /* Parsing context */
001440 ExprList *pList, /* List to which to append. Might be NULL */
001441 Expr *pExpr /* Expression to be appended. Might be NULL */
001442 ){
001443 sqlite3 *db = pParse->db;
001444 assert( db!=0 );
001445 if( pList==0 ){
001446 pList = sqlite3DbMallocRawNN(db, sizeof(ExprList) );
001447 if( pList==0 ){
001448 goto no_mem;
001449 }
001450 pList->nExpr = 0;
001451 pList->a = sqlite3DbMallocRawNN(db, sizeof(pList->a[0]));
001452 if( pList->a==0 ) goto no_mem;
001453 }else if( (pList->nExpr & (pList->nExpr-1))==0 ){
001454 struct ExprList_item *a;
001455 assert( pList->nExpr>0 );
001456 a = sqlite3DbRealloc(db, pList->a, pList->nExpr*2*sizeof(pList->a[0]));
001457 if( a==0 ){
001458 goto no_mem;
001459 }
001460 pList->a = a;
001461 }
001462 assert( pList->a!=0 );
001463 if( 1 ){
001464 struct ExprList_item *pItem = &pList->a[pList->nExpr++];
001465 memset(pItem, 0, sizeof(*pItem));
001466 pItem->pExpr = pExpr;
001467 }
001468 return pList;
001469
001470 no_mem:
001471 /* Avoid leaking memory if malloc has failed. */
001472 sqlite3ExprDelete(db, pExpr);
001473 sqlite3ExprListDelete(db, pList);
001474 return 0;
001475 }
001476
001477 /*
001478 ** pColumns and pExpr form a vector assignment which is part of the SET
001479 ** clause of an UPDATE statement. Like this:
001480 **
001481 ** (a,b,c) = (expr1,expr2,expr3)
001482 ** Or: (a,b,c) = (SELECT x,y,z FROM ....)
001483 **
001484 ** For each term of the vector assignment, append new entries to the
001485 ** expression list pList. In the case of a subquery on the LHS, append
001486 ** TK_SELECT_COLUMN expressions.
001487 */
001488 ExprList *sqlite3ExprListAppendVector(
001489 Parse *pParse, /* Parsing context */
001490 ExprList *pList, /* List to which to append. Might be NULL */
001491 IdList *pColumns, /* List of names of LHS of the assignment */
001492 Expr *pExpr /* Vector expression to be appended. Might be NULL */
001493 ){
001494 sqlite3 *db = pParse->db;
001495 int n;
001496 int i;
001497 int iFirst = pList ? pList->nExpr : 0;
001498 /* pColumns can only be NULL due to an OOM but an OOM will cause an
001499 ** exit prior to this routine being invoked */
001500 if( NEVER(pColumns==0) ) goto vector_append_error;
001501 if( pExpr==0 ) goto vector_append_error;
001502 n = sqlite3ExprVectorSize(pExpr);
001503 if( pColumns->nId!=n ){
001504 sqlite3ErrorMsg(pParse, "%d columns assigned %d values",
001505 pColumns->nId, n);
001506 goto vector_append_error;
001507 }
001508 for(i=0; i<n; i++){
001509 Expr *pSubExpr = sqlite3ExprForVectorField(pParse, pExpr, i);
001510 pList = sqlite3ExprListAppend(pParse, pList, pSubExpr);
001511 if( pList ){
001512 assert( pList->nExpr==iFirst+i+1 );
001513 pList->a[pList->nExpr-1].zName = pColumns->a[i].zName;
001514 pColumns->a[i].zName = 0;
001515 }
001516 }
001517 if( pExpr->op==TK_SELECT ){
001518 if( pList && pList->a[iFirst].pExpr ){
001519 assert( pList->a[iFirst].pExpr->op==TK_SELECT_COLUMN );
001520 pList->a[iFirst].pExpr->pRight = pExpr;
001521 pExpr = 0;
001522 }
001523 }
001524
001525 vector_append_error:
001526 sqlite3ExprDelete(db, pExpr);
001527 sqlite3IdListDelete(db, pColumns);
001528 return pList;
001529 }
001530
001531 /*
001532 ** Set the sort order for the last element on the given ExprList.
001533 */
001534 void sqlite3ExprListSetSortOrder(ExprList *p, int iSortOrder){
001535 if( p==0 ) return;
001536 assert( SQLITE_SO_UNDEFINED<0 && SQLITE_SO_ASC>=0 && SQLITE_SO_DESC>0 );
001537 assert( p->nExpr>0 );
001538 if( iSortOrder<0 ){
001539 assert( p->a[p->nExpr-1].sortOrder==SQLITE_SO_ASC );
001540 return;
001541 }
001542 p->a[p->nExpr-1].sortOrder = (u8)iSortOrder;
001543 }
001544
001545 /*
001546 ** Set the ExprList.a[].zName element of the most recently added item
001547 ** on the expression list.
001548 **
001549 ** pList might be NULL following an OOM error. But pName should never be
001550 ** NULL. If a memory allocation fails, the pParse->db->mallocFailed flag
001551 ** is set.
001552 */
001553 void sqlite3ExprListSetName(
001554 Parse *pParse, /* Parsing context */
001555 ExprList *pList, /* List to which to add the span. */
001556 Token *pName, /* Name to be added */
001557 int dequote /* True to cause the name to be dequoted */
001558 ){
001559 assert( pList!=0 || pParse->db->mallocFailed!=0 );
001560 if( pList ){
001561 struct ExprList_item *pItem;
001562 assert( pList->nExpr>0 );
001563 pItem = &pList->a[pList->nExpr-1];
001564 assert( pItem->zName==0 );
001565 pItem->zName = sqlite3DbStrNDup(pParse->db, pName->z, pName->n);
001566 if( dequote ) sqlite3Dequote(pItem->zName);
001567 }
001568 }
001569
001570 /*
001571 ** Set the ExprList.a[].zSpan element of the most recently added item
001572 ** on the expression list.
001573 **
001574 ** pList might be NULL following an OOM error. But pSpan should never be
001575 ** NULL. If a memory allocation fails, the pParse->db->mallocFailed flag
001576 ** is set.
001577 */
001578 void sqlite3ExprListSetSpan(
001579 Parse *pParse, /* Parsing context */
001580 ExprList *pList, /* List to which to add the span. */
001581 ExprSpan *pSpan /* The span to be added */
001582 ){
001583 sqlite3 *db = pParse->db;
001584 assert( pList!=0 || db->mallocFailed!=0 );
001585 if( pList ){
001586 struct ExprList_item *pItem = &pList->a[pList->nExpr-1];
001587 assert( pList->nExpr>0 );
001588 assert( db->mallocFailed || pItem->pExpr==pSpan->pExpr );
001589 sqlite3DbFree(db, pItem->zSpan);
001590 pItem->zSpan = sqlite3DbStrNDup(db, (char*)pSpan->zStart,
001591 (int)(pSpan->zEnd - pSpan->zStart));
001592 }
001593 }
001594
001595 /*
001596 ** If the expression list pEList contains more than iLimit elements,
001597 ** leave an error message in pParse.
001598 */
001599 void sqlite3ExprListCheckLength(
001600 Parse *pParse,
001601 ExprList *pEList,
001602 const char *zObject
001603 ){
001604 int mx = pParse->db->aLimit[SQLITE_LIMIT_COLUMN];
001605 testcase( pEList && pEList->nExpr==mx );
001606 testcase( pEList && pEList->nExpr==mx+1 );
001607 if( pEList && pEList->nExpr>mx ){
001608 sqlite3ErrorMsg(pParse, "too many columns in %s", zObject);
001609 }
001610 }
001611
001612 /*
001613 ** Delete an entire expression list.
001614 */
001615 static SQLITE_NOINLINE void exprListDeleteNN(sqlite3 *db, ExprList *pList){
001616 int i;
001617 struct ExprList_item *pItem;
001618 assert( pList->a!=0 || pList->nExpr==0 );
001619 for(pItem=pList->a, i=0; i<pList->nExpr; i++, pItem++){
001620 sqlite3ExprDelete(db, pItem->pExpr);
001621 sqlite3DbFree(db, pItem->zName);
001622 sqlite3DbFree(db, pItem->zSpan);
001623 }
001624 sqlite3DbFree(db, pList->a);
001625 sqlite3DbFree(db, pList);
001626 }
001627 void sqlite3ExprListDelete(sqlite3 *db, ExprList *pList){
001628 if( pList ) exprListDeleteNN(db, pList);
001629 }
001630
001631 /*
001632 ** Return the bitwise-OR of all Expr.flags fields in the given
001633 ** ExprList.
001634 */
001635 u32 sqlite3ExprListFlags(const ExprList *pList){
001636 int i;
001637 u32 m = 0;
001638 if( pList ){
001639 for(i=0; i<pList->nExpr; i++){
001640 Expr *pExpr = pList->a[i].pExpr;
001641 assert( pExpr!=0 );
001642 m |= pExpr->flags;
001643 }
001644 }
001645 return m;
001646 }
001647
001648 /*
001649 ** These routines are Walker callbacks used to check expressions to
001650 ** see if they are "constant" for some definition of constant. The
001651 ** Walker.eCode value determines the type of "constant" we are looking
001652 ** for.
001653 **
001654 ** These callback routines are used to implement the following:
001655 **
001656 ** sqlite3ExprIsConstant() pWalker->eCode==1
001657 ** sqlite3ExprIsConstantNotJoin() pWalker->eCode==2
001658 ** sqlite3ExprIsTableConstant() pWalker->eCode==3
001659 ** sqlite3ExprIsConstantOrFunction() pWalker->eCode==4 or 5
001660 **
001661 ** In all cases, the callbacks set Walker.eCode=0 and abort if the expression
001662 ** is found to not be a constant.
001663 **
001664 ** The sqlite3ExprIsConstantOrFunction() is used for evaluating expressions
001665 ** in a CREATE TABLE statement. The Walker.eCode value is 5 when parsing
001666 ** an existing schema and 4 when processing a new statement. A bound
001667 ** parameter raises an error for new statements, but is silently converted
001668 ** to NULL for existing schemas. This allows sqlite_master tables that
001669 ** contain a bound parameter because they were generated by older versions
001670 ** of SQLite to be parsed by newer versions of SQLite without raising a
001671 ** malformed schema error.
001672 */
001673 static int exprNodeIsConstant(Walker *pWalker, Expr *pExpr){
001674
001675 /* If pWalker->eCode is 2 then any term of the expression that comes from
001676 ** the ON or USING clauses of a left join disqualifies the expression
001677 ** from being considered constant. */
001678 if( pWalker->eCode==2 && ExprHasProperty(pExpr, EP_FromJoin) ){
001679 pWalker->eCode = 0;
001680 return WRC_Abort;
001681 }
001682
001683 switch( pExpr->op ){
001684 /* Consider functions to be constant if all their arguments are constant
001685 ** and either pWalker->eCode==4 or 5 or the function has the
001686 ** SQLITE_FUNC_CONST flag. */
001687 case TK_FUNCTION:
001688 if( pWalker->eCode>=4 || ExprHasProperty(pExpr,EP_ConstFunc) ){
001689 return WRC_Continue;
001690 }else{
001691 pWalker->eCode = 0;
001692 return WRC_Abort;
001693 }
001694 case TK_ID:
001695 case TK_COLUMN:
001696 case TK_AGG_FUNCTION:
001697 case TK_AGG_COLUMN:
001698 testcase( pExpr->op==TK_ID );
001699 testcase( pExpr->op==TK_COLUMN );
001700 testcase( pExpr->op==TK_AGG_FUNCTION );
001701 testcase( pExpr->op==TK_AGG_COLUMN );
001702 if( pWalker->eCode==3 && pExpr->iTable==pWalker->u.iCur ){
001703 return WRC_Continue;
001704 }else{
001705 pWalker->eCode = 0;
001706 return WRC_Abort;
001707 }
001708 case TK_VARIABLE:
001709 if( pWalker->eCode==5 ){
001710 /* Silently convert bound parameters that appear inside of CREATE
001711 ** statements into a NULL when parsing the CREATE statement text out
001712 ** of the sqlite_master table */
001713 pExpr->op = TK_NULL;
001714 }else if( pWalker->eCode==4 ){
001715 /* A bound parameter in a CREATE statement that originates from
001716 ** sqlite3_prepare() causes an error */
001717 pWalker->eCode = 0;
001718 return WRC_Abort;
001719 }
001720 /* Fall through */
001721 default:
001722 testcase( pExpr->op==TK_SELECT ); /* selectNodeIsConstant will disallow */
001723 testcase( pExpr->op==TK_EXISTS ); /* selectNodeIsConstant will disallow */
001724 return WRC_Continue;
001725 }
001726 }
001727 static int selectNodeIsConstant(Walker *pWalker, Select *NotUsed){
001728 UNUSED_PARAMETER(NotUsed);
001729 pWalker->eCode = 0;
001730 return WRC_Abort;
001731 }
001732 static int exprIsConst(Expr *p, int initFlag, int iCur){
001733 Walker w;
001734 memset(&w, 0, sizeof(w));
001735 w.eCode = initFlag;
001736 w.xExprCallback = exprNodeIsConstant;
001737 w.xSelectCallback = selectNodeIsConstant;
001738 w.u.iCur = iCur;
001739 sqlite3WalkExpr(&w, p);
001740 return w.eCode;
001741 }
001742
001743 /*
001744 ** Walk an expression tree. Return non-zero if the expression is constant
001745 ** and 0 if it involves variables or function calls.
001746 **
001747 ** For the purposes of this function, a double-quoted string (ex: "abc")
001748 ** is considered a variable but a single-quoted string (ex: 'abc') is
001749 ** a constant.
001750 */
001751 int sqlite3ExprIsConstant(Expr *p){
001752 return exprIsConst(p, 1, 0);
001753 }
001754
001755 /*
001756 ** Walk an expression tree. Return non-zero if the expression is constant
001757 ** that does no originate from the ON or USING clauses of a join.
001758 ** Return 0 if it involves variables or function calls or terms from
001759 ** an ON or USING clause.
001760 */
001761 int sqlite3ExprIsConstantNotJoin(Expr *p){
001762 return exprIsConst(p, 2, 0);
001763 }
001764
001765 /*
001766 ** Walk an expression tree. Return non-zero if the expression is constant
001767 ** for any single row of the table with cursor iCur. In other words, the
001768 ** expression must not refer to any non-deterministic function nor any
001769 ** table other than iCur.
001770 */
001771 int sqlite3ExprIsTableConstant(Expr *p, int iCur){
001772 return exprIsConst(p, 3, iCur);
001773 }
001774
001775 /*
001776 ** Walk an expression tree. Return non-zero if the expression is constant
001777 ** or a function call with constant arguments. Return and 0 if there
001778 ** are any variables.
001779 **
001780 ** For the purposes of this function, a double-quoted string (ex: "abc")
001781 ** is considered a variable but a single-quoted string (ex: 'abc') is
001782 ** a constant.
001783 */
001784 int sqlite3ExprIsConstantOrFunction(Expr *p, u8 isInit){
001785 assert( isInit==0 || isInit==1 );
001786 return exprIsConst(p, 4+isInit, 0);
001787 }
001788
001789 #ifdef SQLITE_ENABLE_CURSOR_HINTS
001790 /*
001791 ** Walk an expression tree. Return 1 if the expression contains a
001792 ** subquery of some kind. Return 0 if there are no subqueries.
001793 */
001794 int sqlite3ExprContainsSubquery(Expr *p){
001795 Walker w;
001796 memset(&w, 0, sizeof(w));
001797 w.eCode = 1;
001798 w.xExprCallback = sqlite3ExprWalkNoop;
001799 w.xSelectCallback = selectNodeIsConstant;
001800 sqlite3WalkExpr(&w, p);
001801 return w.eCode==0;
001802 }
001803 #endif
001804
001805 /*
001806 ** If the expression p codes a constant integer that is small enough
001807 ** to fit in a 32-bit integer, return 1 and put the value of the integer
001808 ** in *pValue. If the expression is not an integer or if it is too big
001809 ** to fit in a signed 32-bit integer, return 0 and leave *pValue unchanged.
001810 */
001811 int sqlite3ExprIsInteger(Expr *p, int *pValue){
001812 int rc = 0;
001813
001814 /* If an expression is an integer literal that fits in a signed 32-bit
001815 ** integer, then the EP_IntValue flag will have already been set */
001816 assert( p->op!=TK_INTEGER || (p->flags & EP_IntValue)!=0
001817 || sqlite3GetInt32(p->u.zToken, &rc)==0 );
001818
001819 if( p->flags & EP_IntValue ){
001820 *pValue = p->u.iValue;
001821 return 1;
001822 }
001823 switch( p->op ){
001824 case TK_UPLUS: {
001825 rc = sqlite3ExprIsInteger(p->pLeft, pValue);
001826 break;
001827 }
001828 case TK_UMINUS: {
001829 int v;
001830 if( sqlite3ExprIsInteger(p->pLeft, &v) ){
001831 assert( v!=(-2147483647-1) );
001832 *pValue = -v;
001833 rc = 1;
001834 }
001835 break;
001836 }
001837 default: break;
001838 }
001839 return rc;
001840 }
001841
001842 /*
001843 ** Return FALSE if there is no chance that the expression can be NULL.
001844 **
001845 ** If the expression might be NULL or if the expression is too complex
001846 ** to tell return TRUE.
001847 **
001848 ** This routine is used as an optimization, to skip OP_IsNull opcodes
001849 ** when we know that a value cannot be NULL. Hence, a false positive
001850 ** (returning TRUE when in fact the expression can never be NULL) might
001851 ** be a small performance hit but is otherwise harmless. On the other
001852 ** hand, a false negative (returning FALSE when the result could be NULL)
001853 ** will likely result in an incorrect answer. So when in doubt, return
001854 ** TRUE.
001855 */
001856 int sqlite3ExprCanBeNull(const Expr *p){
001857 u8 op;
001858 while( p->op==TK_UPLUS || p->op==TK_UMINUS ){ p = p->pLeft; }
001859 op = p->op;
001860 if( op==TK_REGISTER ) op = p->op2;
001861 switch( op ){
001862 case TK_INTEGER:
001863 case TK_STRING:
001864 case TK_FLOAT:
001865 case TK_BLOB:
001866 return 0;
001867 case TK_COLUMN:
001868 assert( p->pTab!=0 );
001869 return ExprHasProperty(p, EP_CanBeNull) ||
001870 (p->iColumn>=0 && p->pTab->aCol[p->iColumn].notNull==0);
001871 default:
001872 return 1;
001873 }
001874 }
001875
001876 /*
001877 ** Return TRUE if the given expression is a constant which would be
001878 ** unchanged by OP_Affinity with the affinity given in the second
001879 ** argument.
001880 **
001881 ** This routine is used to determine if the OP_Affinity operation
001882 ** can be omitted. When in doubt return FALSE. A false negative
001883 ** is harmless. A false positive, however, can result in the wrong
001884 ** answer.
001885 */
001886 int sqlite3ExprNeedsNoAffinityChange(const Expr *p, char aff){
001887 u8 op;
001888 if( aff==SQLITE_AFF_BLOB ) return 1;
001889 while( p->op==TK_UPLUS || p->op==TK_UMINUS ){ p = p->pLeft; }
001890 op = p->op;
001891 if( op==TK_REGISTER ) op = p->op2;
001892 switch( op ){
001893 case TK_INTEGER: {
001894 return aff==SQLITE_AFF_INTEGER || aff==SQLITE_AFF_NUMERIC;
001895 }
001896 case TK_FLOAT: {
001897 return aff==SQLITE_AFF_REAL || aff==SQLITE_AFF_NUMERIC;
001898 }
001899 case TK_STRING: {
001900 return aff==SQLITE_AFF_TEXT;
001901 }
001902 case TK_BLOB: {
001903 return 1;
001904 }
001905 case TK_COLUMN: {
001906 assert( p->iTable>=0 ); /* p cannot be part of a CHECK constraint */
001907 return p->iColumn<0
001908 && (aff==SQLITE_AFF_INTEGER || aff==SQLITE_AFF_NUMERIC);
001909 }
001910 default: {
001911 return 0;
001912 }
001913 }
001914 }
001915
001916 /*
001917 ** Return TRUE if the given string is a row-id column name.
001918 */
001919 int sqlite3IsRowid(const char *z){
001920 if( sqlite3StrICmp(z, "_ROWID_")==0 ) return 1;
001921 if( sqlite3StrICmp(z, "ROWID")==0 ) return 1;
001922 if( sqlite3StrICmp(z, "OID")==0 ) return 1;
001923 return 0;
001924 }
001925
001926 /*
001927 ** pX is the RHS of an IN operator. If pX is a SELECT statement
001928 ** that can be simplified to a direct table access, then return
001929 ** a pointer to the SELECT statement. If pX is not a SELECT statement,
001930 ** or if the SELECT statement needs to be manifested into a transient
001931 ** table, then return NULL.
001932 */
001933 #ifndef SQLITE_OMIT_SUBQUERY
001934 static Select *isCandidateForInOpt(Expr *pX){
001935 Select *p;
001936 SrcList *pSrc;
001937 ExprList *pEList;
001938 Table *pTab;
001939 int i;
001940 if( !ExprHasProperty(pX, EP_xIsSelect) ) return 0; /* Not a subquery */
001941 if( ExprHasProperty(pX, EP_VarSelect) ) return 0; /* Correlated subq */
001942 p = pX->x.pSelect;
001943 if( p->pPrior ) return 0; /* Not a compound SELECT */
001944 if( p->selFlags & (SF_Distinct|SF_Aggregate) ){
001945 testcase( (p->selFlags & (SF_Distinct|SF_Aggregate))==SF_Distinct );
001946 testcase( (p->selFlags & (SF_Distinct|SF_Aggregate))==SF_Aggregate );
001947 return 0; /* No DISTINCT keyword and no aggregate functions */
001948 }
001949 assert( p->pGroupBy==0 ); /* Has no GROUP BY clause */
001950 if( p->pLimit ) return 0; /* Has no LIMIT clause */
001951 assert( p->pOffset==0 ); /* No LIMIT means no OFFSET */
001952 if( p->pWhere ) return 0; /* Has no WHERE clause */
001953 pSrc = p->pSrc;
001954 assert( pSrc!=0 );
001955 if( pSrc->nSrc!=1 ) return 0; /* Single term in FROM clause */
001956 if( pSrc->a[0].pSelect ) return 0; /* FROM is not a subquery or view */
001957 pTab = pSrc->a[0].pTab;
001958 assert( pTab!=0 );
001959 assert( pTab->pSelect==0 ); /* FROM clause is not a view */
001960 if( IsVirtual(pTab) ) return 0; /* FROM clause not a virtual table */
001961 pEList = p->pEList;
001962 assert( pEList!=0 );
001963 /* All SELECT results must be columns. */
001964 for(i=0; i<pEList->nExpr; i++){
001965 Expr *pRes = pEList->a[i].pExpr;
001966 if( pRes->op!=TK_COLUMN ) return 0;
001967 assert( pRes->iTable==pSrc->a[0].iCursor ); /* Not a correlated subquery */
001968 }
001969 return p;
001970 }
001971 #endif /* SQLITE_OMIT_SUBQUERY */
001972
001973 #ifndef SQLITE_OMIT_SUBQUERY
001974 /*
001975 ** Generate code that checks the left-most column of index table iCur to see if
001976 ** it contains any NULL entries. Cause the register at regHasNull to be set
001977 ** to a non-NULL value if iCur contains no NULLs. Cause register regHasNull
001978 ** to be set to NULL if iCur contains one or more NULL values.
001979 */
001980 static void sqlite3SetHasNullFlag(Vdbe *v, int iCur, int regHasNull){
001981 int addr1;
001982 sqlite3VdbeAddOp2(v, OP_Integer, 0, regHasNull);
001983 addr1 = sqlite3VdbeAddOp1(v, OP_Rewind, iCur); VdbeCoverage(v);
001984 sqlite3VdbeAddOp3(v, OP_Column, iCur, 0, regHasNull);
001985 sqlite3VdbeChangeP5(v, OPFLAG_TYPEOFARG);
001986 VdbeComment((v, "first_entry_in(%d)", iCur));
001987 sqlite3VdbeJumpHere(v, addr1);
001988 }
001989 #endif
001990
001991
001992 #ifndef SQLITE_OMIT_SUBQUERY
001993 /*
001994 ** The argument is an IN operator with a list (not a subquery) on the
001995 ** right-hand side. Return TRUE if that list is constant.
001996 */
001997 static int sqlite3InRhsIsConstant(Expr *pIn){
001998 Expr *pLHS;
001999 int res;
002000 assert( !ExprHasProperty(pIn, EP_xIsSelect) );
002001 pLHS = pIn->pLeft;
002002 pIn->pLeft = 0;
002003 res = sqlite3ExprIsConstant(pIn);
002004 pIn->pLeft = pLHS;
002005 return res;
002006 }
002007 #endif
002008
002009 /*
002010 ** This function is used by the implementation of the IN (...) operator.
002011 ** The pX parameter is the expression on the RHS of the IN operator, which
002012 ** might be either a list of expressions or a subquery.
002013 **
002014 ** The job of this routine is to find or create a b-tree object that can
002015 ** be used either to test for membership in the RHS set or to iterate through
002016 ** all members of the RHS set, skipping duplicates.
002017 **
002018 ** A cursor is opened on the b-tree object that is the RHS of the IN operator
002019 ** and pX->iTable is set to the index of that cursor.
002020 **
002021 ** The returned value of this function indicates the b-tree type, as follows:
002022 **
002023 ** IN_INDEX_ROWID - The cursor was opened on a database table.
002024 ** IN_INDEX_INDEX_ASC - The cursor was opened on an ascending index.
002025 ** IN_INDEX_INDEX_DESC - The cursor was opened on a descending index.
002026 ** IN_INDEX_EPH - The cursor was opened on a specially created and
002027 ** populated epheremal table.
002028 ** IN_INDEX_NOOP - No cursor was allocated. The IN operator must be
002029 ** implemented as a sequence of comparisons.
002030 **
002031 ** An existing b-tree might be used if the RHS expression pX is a simple
002032 ** subquery such as:
002033 **
002034 ** SELECT <column1>, <column2>... FROM <table>
002035 **
002036 ** If the RHS of the IN operator is a list or a more complex subquery, then
002037 ** an ephemeral table might need to be generated from the RHS and then
002038 ** pX->iTable made to point to the ephemeral table instead of an
002039 ** existing table.
002040 **
002041 ** The inFlags parameter must contain exactly one of the bits
002042 ** IN_INDEX_MEMBERSHIP or IN_INDEX_LOOP. If inFlags contains
002043 ** IN_INDEX_MEMBERSHIP, then the generated table will be used for a
002044 ** fast membership test. When the IN_INDEX_LOOP bit is set, the
002045 ** IN index will be used to loop over all values of the RHS of the
002046 ** IN operator.
002047 **
002048 ** When IN_INDEX_LOOP is used (and the b-tree will be used to iterate
002049 ** through the set members) then the b-tree must not contain duplicates.
002050 ** An epheremal table must be used unless the selected columns are guaranteed
002051 ** to be unique - either because it is an INTEGER PRIMARY KEY or due to
002052 ** a UNIQUE constraint or index.
002053 **
002054 ** When IN_INDEX_MEMBERSHIP is used (and the b-tree will be used
002055 ** for fast set membership tests) then an epheremal table must
002056 ** be used unless <columns> is a single INTEGER PRIMARY KEY column or an
002057 ** index can be found with the specified <columns> as its left-most.
002058 **
002059 ** If the IN_INDEX_NOOP_OK and IN_INDEX_MEMBERSHIP are both set and
002060 ** if the RHS of the IN operator is a list (not a subquery) then this
002061 ** routine might decide that creating an ephemeral b-tree for membership
002062 ** testing is too expensive and return IN_INDEX_NOOP. In that case, the
002063 ** calling routine should implement the IN operator using a sequence
002064 ** of Eq or Ne comparison operations.
002065 **
002066 ** When the b-tree is being used for membership tests, the calling function
002067 ** might need to know whether or not the RHS side of the IN operator
002068 ** contains a NULL. If prRhsHasNull is not a NULL pointer and
002069 ** if there is any chance that the (...) might contain a NULL value at
002070 ** runtime, then a register is allocated and the register number written
002071 ** to *prRhsHasNull. If there is no chance that the (...) contains a
002072 ** NULL value, then *prRhsHasNull is left unchanged.
002073 **
002074 ** If a register is allocated and its location stored in *prRhsHasNull, then
002075 ** the value in that register will be NULL if the b-tree contains one or more
002076 ** NULL values, and it will be some non-NULL value if the b-tree contains no
002077 ** NULL values.
002078 **
002079 ** If the aiMap parameter is not NULL, it must point to an array containing
002080 ** one element for each column returned by the SELECT statement on the RHS
002081 ** of the IN(...) operator. The i'th entry of the array is populated with the
002082 ** offset of the index column that matches the i'th column returned by the
002083 ** SELECT. For example, if the expression and selected index are:
002084 **
002085 ** (?,?,?) IN (SELECT a, b, c FROM t1)
002086 ** CREATE INDEX i1 ON t1(b, c, a);
002087 **
002088 ** then aiMap[] is populated with {2, 0, 1}.
002089 */
002090 #ifndef SQLITE_OMIT_SUBQUERY
002091 int sqlite3FindInIndex(
002092 Parse *pParse, /* Parsing context */
002093 Expr *pX, /* The right-hand side (RHS) of the IN operator */
002094 u32 inFlags, /* IN_INDEX_LOOP, _MEMBERSHIP, and/or _NOOP_OK */
002095 int *prRhsHasNull, /* Register holding NULL status. See notes */
002096 int *aiMap /* Mapping from Index fields to RHS fields */
002097 ){
002098 Select *p; /* SELECT to the right of IN operator */
002099 int eType = 0; /* Type of RHS table. IN_INDEX_* */
002100 int iTab = pParse->nTab++; /* Cursor of the RHS table */
002101 int mustBeUnique; /* True if RHS must be unique */
002102 Vdbe *v = sqlite3GetVdbe(pParse); /* Virtual machine being coded */
002103
002104 assert( pX->op==TK_IN );
002105 mustBeUnique = (inFlags & IN_INDEX_LOOP)!=0;
002106
002107 /* If the RHS of this IN(...) operator is a SELECT, and if it matters
002108 ** whether or not the SELECT result contains NULL values, check whether
002109 ** or not NULL is actually possible (it may not be, for example, due
002110 ** to NOT NULL constraints in the schema). If no NULL values are possible,
002111 ** set prRhsHasNull to 0 before continuing. */
002112 if( prRhsHasNull && (pX->flags & EP_xIsSelect) ){
002113 int i;
002114 ExprList *pEList = pX->x.pSelect->pEList;
002115 for(i=0; i<pEList->nExpr; i++){
002116 if( sqlite3ExprCanBeNull(pEList->a[i].pExpr) ) break;
002117 }
002118 if( i==pEList->nExpr ){
002119 prRhsHasNull = 0;
002120 }
002121 }
002122
002123 /* Check to see if an existing table or index can be used to
002124 ** satisfy the query. This is preferable to generating a new
002125 ** ephemeral table. */
002126 if( pParse->nErr==0 && (p = isCandidateForInOpt(pX))!=0 ){
002127 sqlite3 *db = pParse->db; /* Database connection */
002128 Table *pTab; /* Table <table>. */
002129 i16 iDb; /* Database idx for pTab */
002130 ExprList *pEList = p->pEList;
002131 int nExpr = pEList->nExpr;
002132
002133 assert( p->pEList!=0 ); /* Because of isCandidateForInOpt(p) */
002134 assert( p->pEList->a[0].pExpr!=0 ); /* Because of isCandidateForInOpt(p) */
002135 assert( p->pSrc!=0 ); /* Because of isCandidateForInOpt(p) */
002136 pTab = p->pSrc->a[0].pTab;
002137
002138 /* Code an OP_Transaction and OP_TableLock for <table>. */
002139 iDb = sqlite3SchemaToIndex(db, pTab->pSchema);
002140 sqlite3CodeVerifySchema(pParse, iDb);
002141 sqlite3TableLock(pParse, iDb, pTab->tnum, 0, pTab->zName);
002142
002143 assert(v); /* sqlite3GetVdbe() has always been previously called */
002144 if( nExpr==1 && pEList->a[0].pExpr->iColumn<0 ){
002145 /* The "x IN (SELECT rowid FROM table)" case */
002146 int iAddr = sqlite3VdbeAddOp0(v, OP_Once);
002147 VdbeCoverage(v);
002148
002149 sqlite3OpenTable(pParse, iTab, iDb, pTab, OP_OpenRead);
002150 eType = IN_INDEX_ROWID;
002151
002152 sqlite3VdbeJumpHere(v, iAddr);
002153 }else{
002154 Index *pIdx; /* Iterator variable */
002155 int affinity_ok = 1;
002156 int i;
002157
002158 /* Check that the affinity that will be used to perform each
002159 ** comparison is the same as the affinity of each column in table
002160 ** on the RHS of the IN operator. If it not, it is not possible to
002161 ** use any index of the RHS table. */
002162 for(i=0; i<nExpr && affinity_ok; i++){
002163 Expr *pLhs = sqlite3VectorFieldSubexpr(pX->pLeft, i);
002164 int iCol = pEList->a[i].pExpr->iColumn;
002165 char idxaff = sqlite3TableColumnAffinity(pTab,iCol); /* RHS table */
002166 char cmpaff = sqlite3CompareAffinity(pLhs, idxaff);
002167 testcase( cmpaff==SQLITE_AFF_BLOB );
002168 testcase( cmpaff==SQLITE_AFF_TEXT );
002169 switch( cmpaff ){
002170 case SQLITE_AFF_BLOB:
002171 break;
002172 case SQLITE_AFF_TEXT:
002173 /* sqlite3CompareAffinity() only returns TEXT if one side or the
002174 ** other has no affinity and the other side is TEXT. Hence,
002175 ** the only way for cmpaff to be TEXT is for idxaff to be TEXT
002176 ** and for the term on the LHS of the IN to have no affinity. */
002177 assert( idxaff==SQLITE_AFF_TEXT );
002178 break;
002179 default:
002180 affinity_ok = sqlite3IsNumericAffinity(idxaff);
002181 }
002182 }
002183
002184 if( affinity_ok ){
002185 /* Search for an existing index that will work for this IN operator */
002186 for(pIdx=pTab->pIndex; pIdx && eType==0; pIdx=pIdx->pNext){
002187 Bitmask colUsed; /* Columns of the index used */
002188 Bitmask mCol; /* Mask for the current column */
002189 if( pIdx->nColumn<nExpr ) continue;
002190 /* Maximum nColumn is BMS-2, not BMS-1, so that we can compute
002191 ** BITMASK(nExpr) without overflowing */
002192 testcase( pIdx->nColumn==BMS-2 );
002193 testcase( pIdx->nColumn==BMS-1 );
002194 if( pIdx->nColumn>=BMS-1 ) continue;
002195 if( mustBeUnique ){
002196 if( pIdx->nKeyCol>nExpr
002197 ||(pIdx->nColumn>nExpr && !IsUniqueIndex(pIdx))
002198 ){
002199 continue; /* This index is not unique over the IN RHS columns */
002200 }
002201 }
002202
002203 colUsed = 0; /* Columns of index used so far */
002204 for(i=0; i<nExpr; i++){
002205 Expr *pLhs = sqlite3VectorFieldSubexpr(pX->pLeft, i);
002206 Expr *pRhs = pEList->a[i].pExpr;
002207 CollSeq *pReq = sqlite3BinaryCompareCollSeq(pParse, pLhs, pRhs);
002208 int j;
002209
002210 assert( pReq!=0 || pRhs->iColumn==XN_ROWID || pParse->nErr );
002211 for(j=0; j<nExpr; j++){
002212 if( pIdx->aiColumn[j]!=pRhs->iColumn ) continue;
002213 assert( pIdx->azColl[j] );
002214 if( pReq!=0 && sqlite3StrICmp(pReq->zName, pIdx->azColl[j])!=0 ){
002215 continue;
002216 }
002217 break;
002218 }
002219 if( j==nExpr ) break;
002220 mCol = MASKBIT(j);
002221 if( mCol & colUsed ) break; /* Each column used only once */
002222 colUsed |= mCol;
002223 if( aiMap ) aiMap[i] = j;
002224 }
002225
002226 assert( i==nExpr || colUsed!=(MASKBIT(nExpr)-1) );
002227 if( colUsed==(MASKBIT(nExpr)-1) ){
002228 /* If we reach this point, that means the index pIdx is usable */
002229 int iAddr = sqlite3VdbeAddOp0(v, OP_Once); VdbeCoverage(v);
002230 #ifndef SQLITE_OMIT_EXPLAIN
002231 sqlite3VdbeAddOp4(v, OP_Explain, 0, 0, 0,
002232 sqlite3MPrintf(db, "USING INDEX %s FOR IN-OPERATOR",pIdx->zName),
002233 P4_DYNAMIC);
002234 #endif
002235 sqlite3VdbeAddOp3(v, OP_OpenRead, iTab, pIdx->tnum, iDb);
002236 sqlite3VdbeSetP4KeyInfo(pParse, pIdx);
002237 VdbeComment((v, "%s", pIdx->zName));
002238 assert( IN_INDEX_INDEX_DESC == IN_INDEX_INDEX_ASC+1 );
002239 eType = IN_INDEX_INDEX_ASC + pIdx->aSortOrder[0];
002240
002241 if( prRhsHasNull ){
002242 #ifdef SQLITE_ENABLE_COLUMN_USED_MASK
002243 i64 mask = (1<<nExpr)-1;
002244 sqlite3VdbeAddOp4Dup8(v, OP_ColumnsUsed,
002245 iTab, 0, 0, (u8*)&mask, P4_INT64);
002246 #endif
002247 *prRhsHasNull = ++pParse->nMem;
002248 if( nExpr==1 ){
002249 sqlite3SetHasNullFlag(v, iTab, *prRhsHasNull);
002250 }
002251 }
002252 sqlite3VdbeJumpHere(v, iAddr);
002253 }
002254 } /* End loop over indexes */
002255 } /* End if( affinity_ok ) */
002256 } /* End if not an rowid index */
002257 } /* End attempt to optimize using an index */
002258
002259 /* If no preexisting index is available for the IN clause
002260 ** and IN_INDEX_NOOP is an allowed reply
002261 ** and the RHS of the IN operator is a list, not a subquery
002262 ** and the RHS is not constant or has two or fewer terms,
002263 ** then it is not worth creating an ephemeral table to evaluate
002264 ** the IN operator so return IN_INDEX_NOOP.
002265 */
002266 if( eType==0
002267 && (inFlags & IN_INDEX_NOOP_OK)
002268 && !ExprHasProperty(pX, EP_xIsSelect)
002269 && (!sqlite3InRhsIsConstant(pX) || pX->x.pList->nExpr<=2)
002270 ){
002271 eType = IN_INDEX_NOOP;
002272 }
002273
002274 if( eType==0 ){
002275 /* Could not find an existing table or index to use as the RHS b-tree.
002276 ** We will have to generate an ephemeral table to do the job.
002277 */
002278 u32 savedNQueryLoop = pParse->nQueryLoop;
002279 int rMayHaveNull = 0;
002280 eType = IN_INDEX_EPH;
002281 if( inFlags & IN_INDEX_LOOP ){
002282 pParse->nQueryLoop = 0;
002283 if( pX->pLeft->iColumn<0 && !ExprHasProperty(pX, EP_xIsSelect) ){
002284 eType = IN_INDEX_ROWID;
002285 }
002286 }else if( prRhsHasNull ){
002287 *prRhsHasNull = rMayHaveNull = ++pParse->nMem;
002288 }
002289 sqlite3CodeSubselect(pParse, pX, rMayHaveNull, eType==IN_INDEX_ROWID);
002290 pParse->nQueryLoop = savedNQueryLoop;
002291 }else{
002292 pX->iTable = iTab;
002293 }
002294
002295 if( aiMap && eType!=IN_INDEX_INDEX_ASC && eType!=IN_INDEX_INDEX_DESC ){
002296 int i, n;
002297 n = sqlite3ExprVectorSize(pX->pLeft);
002298 for(i=0; i<n; i++) aiMap[i] = i;
002299 }
002300 return eType;
002301 }
002302 #endif
002303
002304 #ifndef SQLITE_OMIT_SUBQUERY
002305 /*
002306 ** Argument pExpr is an (?, ?...) IN(...) expression. This
002307 ** function allocates and returns a nul-terminated string containing
002308 ** the affinities to be used for each column of the comparison.
002309 **
002310 ** It is the responsibility of the caller to ensure that the returned
002311 ** string is eventually freed using sqlite3DbFree().
002312 */
002313 static char *exprINAffinity(Parse *pParse, Expr *pExpr){
002314 Expr *pLeft = pExpr->pLeft;
002315 int nVal = sqlite3ExprVectorSize(pLeft);
002316 Select *pSelect = (pExpr->flags & EP_xIsSelect) ? pExpr->x.pSelect : 0;
002317 char *zRet;
002318
002319 assert( pExpr->op==TK_IN );
002320 zRet = sqlite3DbMallocZero(pParse->db, nVal+1);
002321 if( zRet ){
002322 int i;
002323 for(i=0; i<nVal; i++){
002324 Expr *pA = sqlite3VectorFieldSubexpr(pLeft, i);
002325 char a = sqlite3ExprAffinity(pA);
002326 if( pSelect ){
002327 zRet[i] = sqlite3CompareAffinity(pSelect->pEList->a[i].pExpr, a);
002328 }else{
002329 zRet[i] = a;
002330 }
002331 }
002332 zRet[nVal] = '\0';
002333 }
002334 return zRet;
002335 }
002336 #endif
002337
002338 #ifndef SQLITE_OMIT_SUBQUERY
002339 /*
002340 ** Load the Parse object passed as the first argument with an error
002341 ** message of the form:
002342 **
002343 ** "sub-select returns N columns - expected M"
002344 */
002345 void sqlite3SubselectError(Parse *pParse, int nActual, int nExpect){
002346 const char *zFmt = "sub-select returns %d columns - expected %d";
002347 sqlite3ErrorMsg(pParse, zFmt, nActual, nExpect);
002348 }
002349 #endif
002350
002351 /*
002352 ** Expression pExpr is a vector that has been used in a context where
002353 ** it is not permitted. If pExpr is a sub-select vector, this routine
002354 ** loads the Parse object with a message of the form:
002355 **
002356 ** "sub-select returns N columns - expected 1"
002357 **
002358 ** Or, if it is a regular scalar vector:
002359 **
002360 ** "row value misused"
002361 */
002362 void sqlite3VectorErrorMsg(Parse *pParse, Expr *pExpr){
002363 #ifndef SQLITE_OMIT_SUBQUERY
002364 if( pExpr->flags & EP_xIsSelect ){
002365 sqlite3SubselectError(pParse, pExpr->x.pSelect->pEList->nExpr, 1);
002366 }else
002367 #endif
002368 {
002369 sqlite3ErrorMsg(pParse, "row value misused");
002370 }
002371 }
002372
002373 /*
002374 ** Generate code for scalar subqueries used as a subquery expression, EXISTS,
002375 ** or IN operators. Examples:
002376 **
002377 ** (SELECT a FROM b) -- subquery
002378 ** EXISTS (SELECT a FROM b) -- EXISTS subquery
002379 ** x IN (4,5,11) -- IN operator with list on right-hand side
002380 ** x IN (SELECT a FROM b) -- IN operator with subquery on the right
002381 **
002382 ** The pExpr parameter describes the expression that contains the IN
002383 ** operator or subquery.
002384 **
002385 ** If parameter isRowid is non-zero, then expression pExpr is guaranteed
002386 ** to be of the form "<rowid> IN (?, ?, ?)", where <rowid> is a reference
002387 ** to some integer key column of a table B-Tree. In this case, use an
002388 ** intkey B-Tree to store the set of IN(...) values instead of the usual
002389 ** (slower) variable length keys B-Tree.
002390 **
002391 ** If rMayHaveNull is non-zero, that means that the operation is an IN
002392 ** (not a SELECT or EXISTS) and that the RHS might contains NULLs.
002393 ** All this routine does is initialize the register given by rMayHaveNull
002394 ** to NULL. Calling routines will take care of changing this register
002395 ** value to non-NULL if the RHS is NULL-free.
002396 **
002397 ** For a SELECT or EXISTS operator, return the register that holds the
002398 ** result. For a multi-column SELECT, the result is stored in a contiguous
002399 ** array of registers and the return value is the register of the left-most
002400 ** result column. Return 0 for IN operators or if an error occurs.
002401 */
002402 #ifndef SQLITE_OMIT_SUBQUERY
002403 int sqlite3CodeSubselect(
002404 Parse *pParse, /* Parsing context */
002405 Expr *pExpr, /* The IN, SELECT, or EXISTS operator */
002406 int rHasNullFlag, /* Register that records whether NULLs exist in RHS */
002407 int isRowid /* If true, LHS of IN operator is a rowid */
002408 ){
002409 int jmpIfDynamic = -1; /* One-time test address */
002410 int rReg = 0; /* Register storing resulting */
002411 Vdbe *v = sqlite3GetVdbe(pParse);
002412 if( NEVER(v==0) ) return 0;
002413 sqlite3ExprCachePush(pParse);
002414
002415 /* The evaluation of the IN/EXISTS/SELECT must be repeated every time it
002416 ** is encountered if any of the following is true:
002417 **
002418 ** * The right-hand side is a correlated subquery
002419 ** * The right-hand side is an expression list containing variables
002420 ** * We are inside a trigger
002421 **
002422 ** If all of the above are false, then we can run this code just once
002423 ** save the results, and reuse the same result on subsequent invocations.
002424 */
002425 if( !ExprHasProperty(pExpr, EP_VarSelect) ){
002426 jmpIfDynamic = sqlite3VdbeAddOp0(v, OP_Once); VdbeCoverage(v);
002427 }
002428
002429 #ifndef SQLITE_OMIT_EXPLAIN
002430 if( pParse->explain==2 ){
002431 char *zMsg = sqlite3MPrintf(pParse->db, "EXECUTE %s%s SUBQUERY %d",
002432 jmpIfDynamic>=0?"":"CORRELATED ",
002433 pExpr->op==TK_IN?"LIST":"SCALAR",
002434 pParse->iNextSelectId
002435 );
002436 sqlite3VdbeAddOp4(v, OP_Explain, pParse->iSelectId, 0, 0, zMsg, P4_DYNAMIC);
002437 }
002438 #endif
002439
002440 switch( pExpr->op ){
002441 case TK_IN: {
002442 int addr; /* Address of OP_OpenEphemeral instruction */
002443 Expr *pLeft = pExpr->pLeft; /* the LHS of the IN operator */
002444 KeyInfo *pKeyInfo = 0; /* Key information */
002445 int nVal; /* Size of vector pLeft */
002446
002447 nVal = sqlite3ExprVectorSize(pLeft);
002448 assert( !isRowid || nVal==1 );
002449
002450 /* Whether this is an 'x IN(SELECT...)' or an 'x IN(<exprlist>)'
002451 ** expression it is handled the same way. An ephemeral table is
002452 ** filled with index keys representing the results from the
002453 ** SELECT or the <exprlist>.
002454 **
002455 ** If the 'x' expression is a column value, or the SELECT...
002456 ** statement returns a column value, then the affinity of that
002457 ** column is used to build the index keys. If both 'x' and the
002458 ** SELECT... statement are columns, then numeric affinity is used
002459 ** if either column has NUMERIC or INTEGER affinity. If neither
002460 ** 'x' nor the SELECT... statement are columns, then numeric affinity
002461 ** is used.
002462 */
002463 pExpr->iTable = pParse->nTab++;
002464 addr = sqlite3VdbeAddOp2(v, OP_OpenEphemeral,
002465 pExpr->iTable, (isRowid?0:nVal));
002466 pKeyInfo = isRowid ? 0 : sqlite3KeyInfoAlloc(pParse->db, nVal, 1);
002467
002468 if( ExprHasProperty(pExpr, EP_xIsSelect) ){
002469 /* Case 1: expr IN (SELECT ...)
002470 **
002471 ** Generate code to write the results of the select into the temporary
002472 ** table allocated and opened above.
002473 */
002474 Select *pSelect = pExpr->x.pSelect;
002475 ExprList *pEList = pSelect->pEList;
002476
002477 assert( !isRowid );
002478 /* If the LHS and RHS of the IN operator do not match, that
002479 ** error will have been caught long before we reach this point. */
002480 if( ALWAYS(pEList->nExpr==nVal) ){
002481 SelectDest dest;
002482 int i;
002483 sqlite3SelectDestInit(&dest, SRT_Set, pExpr->iTable);
002484 dest.zAffSdst = exprINAffinity(pParse, pExpr);
002485 assert( (pExpr->iTable&0x0000FFFF)==pExpr->iTable );
002486 pSelect->iLimit = 0;
002487 testcase( pSelect->selFlags & SF_Distinct );
002488 testcase( pKeyInfo==0 ); /* Caused by OOM in sqlite3KeyInfoAlloc() */
002489 if( sqlite3Select(pParse, pSelect, &dest) ){
002490 sqlite3DbFree(pParse->db, dest.zAffSdst);
002491 sqlite3KeyInfoUnref(pKeyInfo);
002492 return 0;
002493 }
002494 sqlite3DbFree(pParse->db, dest.zAffSdst);
002495 assert( pKeyInfo!=0 ); /* OOM will cause exit after sqlite3Select() */
002496 assert( pEList!=0 );
002497 assert( pEList->nExpr>0 );
002498 assert( sqlite3KeyInfoIsWriteable(pKeyInfo) );
002499 for(i=0; i<nVal; i++){
002500 Expr *p = sqlite3VectorFieldSubexpr(pLeft, i);
002501 pKeyInfo->aColl[i] = sqlite3BinaryCompareCollSeq(
002502 pParse, p, pEList->a[i].pExpr
002503 );
002504 }
002505 }
002506 }else if( ALWAYS(pExpr->x.pList!=0) ){
002507 /* Case 2: expr IN (exprlist)
002508 **
002509 ** For each expression, build an index key from the evaluation and
002510 ** store it in the temporary table. If <expr> is a column, then use
002511 ** that columns affinity when building index keys. If <expr> is not
002512 ** a column, use numeric affinity.
002513 */
002514 char affinity; /* Affinity of the LHS of the IN */
002515 int i;
002516 ExprList *pList = pExpr->x.pList;
002517 struct ExprList_item *pItem;
002518 int r1, r2, r3;
002519
002520 affinity = sqlite3ExprAffinity(pLeft);
002521 if( !affinity ){
002522 affinity = SQLITE_AFF_BLOB;
002523 }
002524 if( pKeyInfo ){
002525 assert( sqlite3KeyInfoIsWriteable(pKeyInfo) );
002526 pKeyInfo->aColl[0] = sqlite3ExprCollSeq(pParse, pExpr->pLeft);
002527 }
002528
002529 /* Loop through each expression in <exprlist>. */
002530 r1 = sqlite3GetTempReg(pParse);
002531 r2 = sqlite3GetTempReg(pParse);
002532 if( isRowid ) sqlite3VdbeAddOp2(v, OP_Null, 0, r2);
002533 for(i=pList->nExpr, pItem=pList->a; i>0; i--, pItem++){
002534 Expr *pE2 = pItem->pExpr;
002535 int iValToIns;
002536
002537 /* If the expression is not constant then we will need to
002538 ** disable the test that was generated above that makes sure
002539 ** this code only executes once. Because for a non-constant
002540 ** expression we need to rerun this code each time.
002541 */
002542 if( jmpIfDynamic>=0 && !sqlite3ExprIsConstant(pE2) ){
002543 sqlite3VdbeChangeToNoop(v, jmpIfDynamic);
002544 jmpIfDynamic = -1;
002545 }
002546
002547 /* Evaluate the expression and insert it into the temp table */
002548 if( isRowid && sqlite3ExprIsInteger(pE2, &iValToIns) ){
002549 sqlite3VdbeAddOp3(v, OP_InsertInt, pExpr->iTable, r2, iValToIns);
002550 }else{
002551 r3 = sqlite3ExprCodeTarget(pParse, pE2, r1);
002552 if( isRowid ){
002553 sqlite3VdbeAddOp2(v, OP_MustBeInt, r3,
002554 sqlite3VdbeCurrentAddr(v)+2);
002555 VdbeCoverage(v);
002556 sqlite3VdbeAddOp3(v, OP_Insert, pExpr->iTable, r2, r3);
002557 }else{
002558 sqlite3VdbeAddOp4(v, OP_MakeRecord, r3, 1, r2, &affinity, 1);
002559 sqlite3ExprCacheAffinityChange(pParse, r3, 1);
002560 sqlite3VdbeAddOp4Int(v, OP_IdxInsert, pExpr->iTable, r2, r3, 1);
002561 }
002562 }
002563 }
002564 sqlite3ReleaseTempReg(pParse, r1);
002565 sqlite3ReleaseTempReg(pParse, r2);
002566 }
002567 if( pKeyInfo ){
002568 sqlite3VdbeChangeP4(v, addr, (void *)pKeyInfo, P4_KEYINFO);
002569 }
002570 break;
002571 }
002572
002573 case TK_EXISTS:
002574 case TK_SELECT:
002575 default: {
002576 /* Case 3: (SELECT ... FROM ...)
002577 ** or: EXISTS(SELECT ... FROM ...)
002578 **
002579 ** For a SELECT, generate code to put the values for all columns of
002580 ** the first row into an array of registers and return the index of
002581 ** the first register.
002582 **
002583 ** If this is an EXISTS, write an integer 0 (not exists) or 1 (exists)
002584 ** into a register and return that register number.
002585 **
002586 ** In both cases, the query is augmented with "LIMIT 1". Any
002587 ** preexisting limit is discarded in place of the new LIMIT 1.
002588 */
002589 Select *pSel; /* SELECT statement to encode */
002590 SelectDest dest; /* How to deal with SELECT result */
002591 int nReg; /* Registers to allocate */
002592
002593 testcase( pExpr->op==TK_EXISTS );
002594 testcase( pExpr->op==TK_SELECT );
002595 assert( pExpr->op==TK_EXISTS || pExpr->op==TK_SELECT );
002596 assert( ExprHasProperty(pExpr, EP_xIsSelect) );
002597
002598 pSel = pExpr->x.pSelect;
002599 nReg = pExpr->op==TK_SELECT ? pSel->pEList->nExpr : 1;
002600 sqlite3SelectDestInit(&dest, 0, pParse->nMem+1);
002601 pParse->nMem += nReg;
002602 if( pExpr->op==TK_SELECT ){
002603 dest.eDest = SRT_Mem;
002604 dest.iSdst = dest.iSDParm;
002605 dest.nSdst = nReg;
002606 sqlite3VdbeAddOp3(v, OP_Null, 0, dest.iSDParm, dest.iSDParm+nReg-1);
002607 VdbeComment((v, "Init subquery result"));
002608 }else{
002609 dest.eDest = SRT_Exists;
002610 sqlite3VdbeAddOp2(v, OP_Integer, 0, dest.iSDParm);
002611 VdbeComment((v, "Init EXISTS result"));
002612 }
002613 sqlite3ExprDelete(pParse->db, pSel->pLimit);
002614 pSel->pLimit = sqlite3ExprAlloc(pParse->db, TK_INTEGER,
002615 &sqlite3IntTokens[1], 0);
002616 pSel->iLimit = 0;
002617 pSel->selFlags &= ~SF_MultiValue;
002618 if( sqlite3Select(pParse, pSel, &dest) ){
002619 return 0;
002620 }
002621 rReg = dest.iSDParm;
002622 ExprSetVVAProperty(pExpr, EP_NoReduce);
002623 break;
002624 }
002625 }
002626
002627 if( rHasNullFlag ){
002628 sqlite3SetHasNullFlag(v, pExpr->iTable, rHasNullFlag);
002629 }
002630
002631 if( jmpIfDynamic>=0 ){
002632 sqlite3VdbeJumpHere(v, jmpIfDynamic);
002633 }
002634 sqlite3ExprCachePop(pParse);
002635
002636 return rReg;
002637 }
002638 #endif /* SQLITE_OMIT_SUBQUERY */
002639
002640 #ifndef SQLITE_OMIT_SUBQUERY
002641 /*
002642 ** Expr pIn is an IN(...) expression. This function checks that the
002643 ** sub-select on the RHS of the IN() operator has the same number of
002644 ** columns as the vector on the LHS. Or, if the RHS of the IN() is not
002645 ** a sub-query, that the LHS is a vector of size 1.
002646 */
002647 int sqlite3ExprCheckIN(Parse *pParse, Expr *pIn){
002648 int nVector = sqlite3ExprVectorSize(pIn->pLeft);
002649 if( (pIn->flags & EP_xIsSelect) ){
002650 if( nVector!=pIn->x.pSelect->pEList->nExpr ){
002651 sqlite3SubselectError(pParse, pIn->x.pSelect->pEList->nExpr, nVector);
002652 return 1;
002653 }
002654 }else if( nVector!=1 ){
002655 sqlite3VectorErrorMsg(pParse, pIn->pLeft);
002656 return 1;
002657 }
002658 return 0;
002659 }
002660 #endif
002661
002662 #ifndef SQLITE_OMIT_SUBQUERY
002663 /*
002664 ** Generate code for an IN expression.
002665 **
002666 ** x IN (SELECT ...)
002667 ** x IN (value, value, ...)
002668 **
002669 ** The left-hand side (LHS) is a scalar or vector expression. The
002670 ** right-hand side (RHS) is an array of zero or more scalar values, or a
002671 ** subquery. If the RHS is a subquery, the number of result columns must
002672 ** match the number of columns in the vector on the LHS. If the RHS is
002673 ** a list of values, the LHS must be a scalar.
002674 **
002675 ** The IN operator is true if the LHS value is contained within the RHS.
002676 ** The result is false if the LHS is definitely not in the RHS. The
002677 ** result is NULL if the presence of the LHS in the RHS cannot be
002678 ** determined due to NULLs.
002679 **
002680 ** This routine generates code that jumps to destIfFalse if the LHS is not
002681 ** contained within the RHS. If due to NULLs we cannot determine if the LHS
002682 ** is contained in the RHS then jump to destIfNull. If the LHS is contained
002683 ** within the RHS then fall through.
002684 **
002685 ** See the separate in-operator.md documentation file in the canonical
002686 ** SQLite source tree for additional information.
002687 */
002688 static void sqlite3ExprCodeIN(
002689 Parse *pParse, /* Parsing and code generating context */
002690 Expr *pExpr, /* The IN expression */
002691 int destIfFalse, /* Jump here if LHS is not contained in the RHS */
002692 int destIfNull /* Jump here if the results are unknown due to NULLs */
002693 ){
002694 int rRhsHasNull = 0; /* Register that is true if RHS contains NULL values */
002695 int eType; /* Type of the RHS */
002696 int rLhs; /* Register(s) holding the LHS values */
002697 int rLhsOrig; /* LHS values prior to reordering by aiMap[] */
002698 Vdbe *v; /* Statement under construction */
002699 int *aiMap = 0; /* Map from vector field to index column */
002700 char *zAff = 0; /* Affinity string for comparisons */
002701 int nVector; /* Size of vectors for this IN operator */
002702 int iDummy; /* Dummy parameter to exprCodeVector() */
002703 Expr *pLeft; /* The LHS of the IN operator */
002704 int i; /* loop counter */
002705 int destStep2; /* Where to jump when NULLs seen in step 2 */
002706 int destStep6 = 0; /* Start of code for Step 6 */
002707 int addrTruthOp; /* Address of opcode that determines the IN is true */
002708 int destNotNull; /* Jump here if a comparison is not true in step 6 */
002709 int addrTop; /* Top of the step-6 loop */
002710
002711 pLeft = pExpr->pLeft;
002712 if( sqlite3ExprCheckIN(pParse, pExpr) ) return;
002713 zAff = exprINAffinity(pParse, pExpr);
002714 nVector = sqlite3ExprVectorSize(pExpr->pLeft);
002715 aiMap = (int*)sqlite3DbMallocZero(
002716 pParse->db, nVector*(sizeof(int) + sizeof(char)) + 1
002717 );
002718 if( pParse->db->mallocFailed ) goto sqlite3ExprCodeIN_oom_error;
002719
002720 /* Attempt to compute the RHS. After this step, if anything other than
002721 ** IN_INDEX_NOOP is returned, the table opened ith cursor pExpr->iTable
002722 ** contains the values that make up the RHS. If IN_INDEX_NOOP is returned,
002723 ** the RHS has not yet been coded. */
002724 v = pParse->pVdbe;
002725 assert( v!=0 ); /* OOM detected prior to this routine */
002726 VdbeNoopComment((v, "begin IN expr"));
002727 eType = sqlite3FindInIndex(pParse, pExpr,
002728 IN_INDEX_MEMBERSHIP | IN_INDEX_NOOP_OK,
002729 destIfFalse==destIfNull ? 0 : &rRhsHasNull, aiMap);
002730
002731 assert( pParse->nErr || nVector==1 || eType==IN_INDEX_EPH
002732 || eType==IN_INDEX_INDEX_ASC || eType==IN_INDEX_INDEX_DESC
002733 );
002734 #ifdef SQLITE_DEBUG
002735 /* Confirm that aiMap[] contains nVector integer values between 0 and
002736 ** nVector-1. */
002737 for(i=0; i<nVector; i++){
002738 int j, cnt;
002739 for(cnt=j=0; j<nVector; j++) if( aiMap[j]==i ) cnt++;
002740 assert( cnt==1 );
002741 }
002742 #endif
002743
002744 /* Code the LHS, the <expr> from "<expr> IN (...)". If the LHS is a
002745 ** vector, then it is stored in an array of nVector registers starting
002746 ** at r1.
002747 **
002748 ** sqlite3FindInIndex() might have reordered the fields of the LHS vector
002749 ** so that the fields are in the same order as an existing index. The
002750 ** aiMap[] array contains a mapping from the original LHS field order to
002751 ** the field order that matches the RHS index.
002752 */
002753 sqlite3ExprCachePush(pParse);
002754 rLhsOrig = exprCodeVector(pParse, pLeft, &iDummy);
002755 for(i=0; i<nVector && aiMap[i]==i; i++){} /* Are LHS fields reordered? */
002756 if( i==nVector ){
002757 /* LHS fields are not reordered */
002758 rLhs = rLhsOrig;
002759 }else{
002760 /* Need to reorder the LHS fields according to aiMap */
002761 rLhs = sqlite3GetTempRange(pParse, nVector);
002762 for(i=0; i<nVector; i++){
002763 sqlite3VdbeAddOp3(v, OP_Copy, rLhsOrig+i, rLhs+aiMap[i], 0);
002764 }
002765 }
002766
002767 /* If sqlite3FindInIndex() did not find or create an index that is
002768 ** suitable for evaluating the IN operator, then evaluate using a
002769 ** sequence of comparisons.
002770 **
002771 ** This is step (1) in the in-operator.md optimized algorithm.
002772 */
002773 if( eType==IN_INDEX_NOOP ){
002774 ExprList *pList = pExpr->x.pList;
002775 CollSeq *pColl = sqlite3ExprCollSeq(pParse, pExpr->pLeft);
002776 int labelOk = sqlite3VdbeMakeLabel(v);
002777 int r2, regToFree;
002778 int regCkNull = 0;
002779 int ii;
002780 assert( !ExprHasProperty(pExpr, EP_xIsSelect) );
002781 if( destIfNull!=destIfFalse ){
002782 regCkNull = sqlite3GetTempReg(pParse);
002783 sqlite3VdbeAddOp3(v, OP_BitAnd, rLhs, rLhs, regCkNull);
002784 }
002785 for(ii=0; ii<pList->nExpr; ii++){
002786 r2 = sqlite3ExprCodeTemp(pParse, pList->a[ii].pExpr, ®ToFree);
002787 if( regCkNull && sqlite3ExprCanBeNull(pList->a[ii].pExpr) ){
002788 sqlite3VdbeAddOp3(v, OP_BitAnd, regCkNull, r2, regCkNull);
002789 }
002790 if( ii<pList->nExpr-1 || destIfNull!=destIfFalse ){
002791 sqlite3VdbeAddOp4(v, OP_Eq, rLhs, labelOk, r2,
002792 (void*)pColl, P4_COLLSEQ);
002793 VdbeCoverageIf(v, ii<pList->nExpr-1);
002794 VdbeCoverageIf(v, ii==pList->nExpr-1);
002795 sqlite3VdbeChangeP5(v, zAff[0]);
002796 }else{
002797 assert( destIfNull==destIfFalse );
002798 sqlite3VdbeAddOp4(v, OP_Ne, rLhs, destIfFalse, r2,
002799 (void*)pColl, P4_COLLSEQ); VdbeCoverage(v);
002800 sqlite3VdbeChangeP5(v, zAff[0] | SQLITE_JUMPIFNULL);
002801 }
002802 sqlite3ReleaseTempReg(pParse, regToFree);
002803 }
002804 if( regCkNull ){
002805 sqlite3VdbeAddOp2(v, OP_IsNull, regCkNull, destIfNull); VdbeCoverage(v);
002806 sqlite3VdbeGoto(v, destIfFalse);
002807 }
002808 sqlite3VdbeResolveLabel(v, labelOk);
002809 sqlite3ReleaseTempReg(pParse, regCkNull);
002810 goto sqlite3ExprCodeIN_finished;
002811 }
002812
002813 /* Step 2: Check to see if the LHS contains any NULL columns. If the
002814 ** LHS does contain NULLs then the result must be either FALSE or NULL.
002815 ** We will then skip the binary search of the RHS.
002816 */
002817 if( destIfNull==destIfFalse ){
002818 destStep2 = destIfFalse;
002819 }else{
002820 destStep2 = destStep6 = sqlite3VdbeMakeLabel(v);
002821 }
002822 for(i=0; i<nVector; i++){
002823 Expr *p = sqlite3VectorFieldSubexpr(pExpr->pLeft, i);
002824 if( sqlite3ExprCanBeNull(p) ){
002825 sqlite3VdbeAddOp2(v, OP_IsNull, rLhs+i, destStep2);
002826 VdbeCoverage(v);
002827 }
002828 }
002829
002830 /* Step 3. The LHS is now known to be non-NULL. Do the binary search
002831 ** of the RHS using the LHS as a probe. If found, the result is
002832 ** true.
002833 */
002834 if( eType==IN_INDEX_ROWID ){
002835 /* In this case, the RHS is the ROWID of table b-tree and so we also
002836 ** know that the RHS is non-NULL. Hence, we combine steps 3 and 4
002837 ** into a single opcode. */
002838 sqlite3VdbeAddOp3(v, OP_SeekRowid, pExpr->iTable, destIfFalse, rLhs);
002839 VdbeCoverage(v);
002840 addrTruthOp = sqlite3VdbeAddOp0(v, OP_Goto); /* Return True */
002841 }else{
002842 sqlite3VdbeAddOp4(v, OP_Affinity, rLhs, nVector, 0, zAff, nVector);
002843 if( destIfFalse==destIfNull ){
002844 /* Combine Step 3 and Step 5 into a single opcode */
002845 sqlite3VdbeAddOp4Int(v, OP_NotFound, pExpr->iTable, destIfFalse,
002846 rLhs, nVector); VdbeCoverage(v);
002847 goto sqlite3ExprCodeIN_finished;
002848 }
002849 /* Ordinary Step 3, for the case where FALSE and NULL are distinct */
002850 addrTruthOp = sqlite3VdbeAddOp4Int(v, OP_Found, pExpr->iTable, 0,
002851 rLhs, nVector); VdbeCoverage(v);
002852 }
002853
002854 /* Step 4. If the RHS is known to be non-NULL and we did not find
002855 ** an match on the search above, then the result must be FALSE.
002856 */
002857 if( rRhsHasNull && nVector==1 ){
002858 sqlite3VdbeAddOp2(v, OP_NotNull, rRhsHasNull, destIfFalse);
002859 VdbeCoverage(v);
002860 }
002861
002862 /* Step 5. If we do not care about the difference between NULL and
002863 ** FALSE, then just return false.
002864 */
002865 if( destIfFalse==destIfNull ) sqlite3VdbeGoto(v, destIfFalse);
002866
002867 /* Step 6: Loop through rows of the RHS. Compare each row to the LHS.
002868 ** If any comparison is NULL, then the result is NULL. If all
002869 ** comparisons are FALSE then the final result is FALSE.
002870 **
002871 ** For a scalar LHS, it is sufficient to check just the first row
002872 ** of the RHS.
002873 */
002874 if( destStep6 ) sqlite3VdbeResolveLabel(v, destStep6);
002875 addrTop = sqlite3VdbeAddOp2(v, OP_Rewind, pExpr->iTable, destIfFalse);
002876 VdbeCoverage(v);
002877 if( nVector>1 ){
002878 destNotNull = sqlite3VdbeMakeLabel(v);
002879 }else{
002880 /* For nVector==1, combine steps 6 and 7 by immediately returning
002881 ** FALSE if the first comparison is not NULL */
002882 destNotNull = destIfFalse;
002883 }
002884 for(i=0; i<nVector; i++){
002885 Expr *p;
002886 CollSeq *pColl;
002887 int r3 = sqlite3GetTempReg(pParse);
002888 p = sqlite3VectorFieldSubexpr(pLeft, i);
002889 pColl = sqlite3ExprCollSeq(pParse, p);
002890 sqlite3VdbeAddOp3(v, OP_Column, pExpr->iTable, i, r3);
002891 sqlite3VdbeAddOp4(v, OP_Ne, rLhs+i, destNotNull, r3,
002892 (void*)pColl, P4_COLLSEQ);
002893 VdbeCoverage(v);
002894 sqlite3ReleaseTempReg(pParse, r3);
002895 }
002896 sqlite3VdbeAddOp2(v, OP_Goto, 0, destIfNull);
002897 if( nVector>1 ){
002898 sqlite3VdbeResolveLabel(v, destNotNull);
002899 sqlite3VdbeAddOp2(v, OP_Next, pExpr->iTable, addrTop+1);
002900 VdbeCoverage(v);
002901
002902 /* Step 7: If we reach this point, we know that the result must
002903 ** be false. */
002904 sqlite3VdbeAddOp2(v, OP_Goto, 0, destIfFalse);
002905 }
002906
002907 /* Jumps here in order to return true. */
002908 sqlite3VdbeJumpHere(v, addrTruthOp);
002909
002910 sqlite3ExprCodeIN_finished:
002911 if( rLhs!=rLhsOrig ) sqlite3ReleaseTempReg(pParse, rLhs);
002912 sqlite3ExprCachePop(pParse);
002913 VdbeComment((v, "end IN expr"));
002914 sqlite3ExprCodeIN_oom_error:
002915 sqlite3DbFree(pParse->db, aiMap);
002916 sqlite3DbFree(pParse->db, zAff);
002917 }
002918 #endif /* SQLITE_OMIT_SUBQUERY */
002919
002920 #ifndef SQLITE_OMIT_FLOATING_POINT
002921 /*
002922 ** Generate an instruction that will put the floating point
002923 ** value described by z[0..n-1] into register iMem.
002924 **
002925 ** The z[] string will probably not be zero-terminated. But the
002926 ** z[n] character is guaranteed to be something that does not look
002927 ** like the continuation of the number.
002928 */
002929 static void codeReal(Vdbe *v, const char *z, int negateFlag, int iMem){
002930 if( ALWAYS(z!=0) ){
002931 double value;
002932 sqlite3AtoF(z, &value, sqlite3Strlen30(z), SQLITE_UTF8);
002933 assert( !sqlite3IsNaN(value) ); /* The new AtoF never returns NaN */
002934 if( negateFlag ) value = -value;
002935 sqlite3VdbeAddOp4Dup8(v, OP_Real, 0, iMem, 0, (u8*)&value, P4_REAL);
002936 }
002937 }
002938 #endif
002939
002940
002941 /*
002942 ** Generate an instruction that will put the integer describe by
002943 ** text z[0..n-1] into register iMem.
002944 **
002945 ** Expr.u.zToken is always UTF8 and zero-terminated.
002946 */
002947 static void codeInteger(Parse *pParse, Expr *pExpr, int negFlag, int iMem){
002948 Vdbe *v = pParse->pVdbe;
002949 if( pExpr->flags & EP_IntValue ){
002950 int i = pExpr->u.iValue;
002951 assert( i>=0 );
002952 if( negFlag ) i = -i;
002953 sqlite3VdbeAddOp2(v, OP_Integer, i, iMem);
002954 }else{
002955 int c;
002956 i64 value;
002957 const char *z = pExpr->u.zToken;
002958 assert( z!=0 );
002959 c = sqlite3DecOrHexToI64(z, &value);
002960 if( c==1 || (c==2 && !negFlag) || (negFlag && value==SMALLEST_INT64)){
002961 #ifdef SQLITE_OMIT_FLOATING_POINT
002962 sqlite3ErrorMsg(pParse, "oversized integer: %s%s", negFlag ? "-" : "", z);
002963 #else
002964 #ifndef SQLITE_OMIT_HEX_INTEGER
002965 if( sqlite3_strnicmp(z,"0x",2)==0 ){
002966 sqlite3ErrorMsg(pParse, "hex literal too big: %s%s", negFlag?"-":"",z);
002967 }else
002968 #endif
002969 {
002970 codeReal(v, z, negFlag, iMem);
002971 }
002972 #endif
002973 }else{
002974 if( negFlag ){ value = c==2 ? SMALLEST_INT64 : -value; }
002975 sqlite3VdbeAddOp4Dup8(v, OP_Int64, 0, iMem, 0, (u8*)&value, P4_INT64);
002976 }
002977 }
002978 }
002979
002980 /*
002981 ** Erase column-cache entry number i
002982 */
002983 static void cacheEntryClear(Parse *pParse, int i){
002984 if( pParse->aColCache[i].tempReg ){
002985 if( pParse->nTempReg<ArraySize(pParse->aTempReg) ){
002986 pParse->aTempReg[pParse->nTempReg++] = pParse->aColCache[i].iReg;
002987 }
002988 }
002989 pParse->nColCache--;
002990 if( i<pParse->nColCache ){
002991 pParse->aColCache[i] = pParse->aColCache[pParse->nColCache];
002992 }
002993 }
002994
002995
002996 /*
002997 ** Record in the column cache that a particular column from a
002998 ** particular table is stored in a particular register.
002999 */
003000 void sqlite3ExprCacheStore(Parse *pParse, int iTab, int iCol, int iReg){
003001 int i;
003002 int minLru;
003003 int idxLru;
003004 struct yColCache *p;
003005
003006 /* Unless an error has occurred, register numbers are always positive. */
003007 assert( iReg>0 || pParse->nErr || pParse->db->mallocFailed );
003008 assert( iCol>=-1 && iCol<32768 ); /* Finite column numbers */
003009
003010 /* The SQLITE_ColumnCache flag disables the column cache. This is used
003011 ** for testing only - to verify that SQLite always gets the same answer
003012 ** with and without the column cache.
003013 */
003014 if( OptimizationDisabled(pParse->db, SQLITE_ColumnCache) ) return;
003015
003016 /* First replace any existing entry.
003017 **
003018 ** Actually, the way the column cache is currently used, we are guaranteed
003019 ** that the object will never already be in cache. Verify this guarantee.
003020 */
003021 #ifndef NDEBUG
003022 for(i=0, p=pParse->aColCache; i<pParse->nColCache; i++, p++){
003023 assert( p->iTable!=iTab || p->iColumn!=iCol );
003024 }
003025 #endif
003026
003027 /* If the cache is already full, delete the least recently used entry */
003028 if( pParse->nColCache>=SQLITE_N_COLCACHE ){
003029 minLru = 0x7fffffff;
003030 idxLru = -1;
003031 for(i=0, p=pParse->aColCache; i<SQLITE_N_COLCACHE; i++, p++){
003032 if( p->lru<minLru ){
003033 idxLru = i;
003034 minLru = p->lru;
003035 }
003036 }
003037 p = &pParse->aColCache[idxLru];
003038 }else{
003039 p = &pParse->aColCache[pParse->nColCache++];
003040 }
003041
003042 /* Add the new entry to the end of the cache */
003043 p->iLevel = pParse->iCacheLevel;
003044 p->iTable = iTab;
003045 p->iColumn = iCol;
003046 p->iReg = iReg;
003047 p->tempReg = 0;
003048 p->lru = pParse->iCacheCnt++;
003049 }
003050
003051 /*
003052 ** Indicate that registers between iReg..iReg+nReg-1 are being overwritten.
003053 ** Purge the range of registers from the column cache.
003054 */
003055 void sqlite3ExprCacheRemove(Parse *pParse, int iReg, int nReg){
003056 int i = 0;
003057 while( i<pParse->nColCache ){
003058 struct yColCache *p = &pParse->aColCache[i];
003059 if( p->iReg >= iReg && p->iReg < iReg+nReg ){
003060 cacheEntryClear(pParse, i);
003061 }else{
003062 i++;
003063 }
003064 }
003065 }
003066
003067 /*
003068 ** Remember the current column cache context. Any new entries added
003069 ** added to the column cache after this call are removed when the
003070 ** corresponding pop occurs.
003071 */
003072 void sqlite3ExprCachePush(Parse *pParse){
003073 pParse->iCacheLevel++;
003074 #ifdef SQLITE_DEBUG
003075 if( pParse->db->flags & SQLITE_VdbeAddopTrace ){
003076 printf("PUSH to %d\n", pParse->iCacheLevel);
003077 }
003078 #endif
003079 }
003080
003081 /*
003082 ** Remove from the column cache any entries that were added since the
003083 ** the previous sqlite3ExprCachePush operation. In other words, restore
003084 ** the cache to the state it was in prior the most recent Push.
003085 */
003086 void sqlite3ExprCachePop(Parse *pParse){
003087 int i = 0;
003088 assert( pParse->iCacheLevel>=1 );
003089 pParse->iCacheLevel--;
003090 #ifdef SQLITE_DEBUG
003091 if( pParse->db->flags & SQLITE_VdbeAddopTrace ){
003092 printf("POP to %d\n", pParse->iCacheLevel);
003093 }
003094 #endif
003095 while( i<pParse->nColCache ){
003096 if( pParse->aColCache[i].iLevel>pParse->iCacheLevel ){
003097 cacheEntryClear(pParse, i);
003098 }else{
003099 i++;
003100 }
003101 }
003102 }
003103
003104 /*
003105 ** When a cached column is reused, make sure that its register is
003106 ** no longer available as a temp register. ticket #3879: that same
003107 ** register might be in the cache in multiple places, so be sure to
003108 ** get them all.
003109 */
003110 static void sqlite3ExprCachePinRegister(Parse *pParse, int iReg){
003111 int i;
003112 struct yColCache *p;
003113 for(i=0, p=pParse->aColCache; i<pParse->nColCache; i++, p++){
003114 if( p->iReg==iReg ){
003115 p->tempReg = 0;
003116 }
003117 }
003118 }
003119
003120 /* Generate code that will load into register regOut a value that is
003121 ** appropriate for the iIdxCol-th column of index pIdx.
003122 */
003123 void sqlite3ExprCodeLoadIndexColumn(
003124 Parse *pParse, /* The parsing context */
003125 Index *pIdx, /* The index whose column is to be loaded */
003126 int iTabCur, /* Cursor pointing to a table row */
003127 int iIdxCol, /* The column of the index to be loaded */
003128 int regOut /* Store the index column value in this register */
003129 ){
003130 i16 iTabCol = pIdx->aiColumn[iIdxCol];
003131 if( iTabCol==XN_EXPR ){
003132 assert( pIdx->aColExpr );
003133 assert( pIdx->aColExpr->nExpr>iIdxCol );
003134 pParse->iSelfTab = iTabCur;
003135 sqlite3ExprCodeCopy(pParse, pIdx->aColExpr->a[iIdxCol].pExpr, regOut);
003136 }else{
003137 sqlite3ExprCodeGetColumnOfTable(pParse->pVdbe, pIdx->pTable, iTabCur,
003138 iTabCol, regOut);
003139 }
003140 }
003141
003142 /*
003143 ** Generate code to extract the value of the iCol-th column of a table.
003144 */
003145 void sqlite3ExprCodeGetColumnOfTable(
003146 Vdbe *v, /* The VDBE under construction */
003147 Table *pTab, /* The table containing the value */
003148 int iTabCur, /* The table cursor. Or the PK cursor for WITHOUT ROWID */
003149 int iCol, /* Index of the column to extract */
003150 int regOut /* Extract the value into this register */
003151 ){
003152 if( iCol<0 || iCol==pTab->iPKey ){
003153 sqlite3VdbeAddOp2(v, OP_Rowid, iTabCur, regOut);
003154 }else{
003155 int op = IsVirtual(pTab) ? OP_VColumn : OP_Column;
003156 int x = iCol;
003157 if( !HasRowid(pTab) && !IsVirtual(pTab) ){
003158 x = sqlite3ColumnOfIndex(sqlite3PrimaryKeyIndex(pTab), iCol);
003159 }
003160 sqlite3VdbeAddOp3(v, op, iTabCur, x, regOut);
003161 }
003162 if( iCol>=0 ){
003163 sqlite3ColumnDefault(v, pTab, iCol, regOut);
003164 }
003165 }
003166
003167 /*
003168 ** Generate code that will extract the iColumn-th column from
003169 ** table pTab and store the column value in a register.
003170 **
003171 ** An effort is made to store the column value in register iReg. This
003172 ** is not garanteeed for GetColumn() - the result can be stored in
003173 ** any register. But the result is guaranteed to land in register iReg
003174 ** for GetColumnToReg().
003175 **
003176 ** There must be an open cursor to pTab in iTable when this routine
003177 ** is called. If iColumn<0 then code is generated that extracts the rowid.
003178 */
003179 int sqlite3ExprCodeGetColumn(
003180 Parse *pParse, /* Parsing and code generating context */
003181 Table *pTab, /* Description of the table we are reading from */
003182 int iColumn, /* Index of the table column */
003183 int iTable, /* The cursor pointing to the table */
003184 int iReg, /* Store results here */
003185 u8 p5 /* P5 value for OP_Column + FLAGS */
003186 ){
003187 Vdbe *v = pParse->pVdbe;
003188 int i;
003189 struct yColCache *p;
003190
003191 for(i=0, p=pParse->aColCache; i<pParse->nColCache; i++, p++){
003192 if( p->iTable==iTable && p->iColumn==iColumn ){
003193 p->lru = pParse->iCacheCnt++;
003194 sqlite3ExprCachePinRegister(pParse, p->iReg);
003195 return p->iReg;
003196 }
003197 }
003198 assert( v!=0 );
003199 sqlite3ExprCodeGetColumnOfTable(v, pTab, iTable, iColumn, iReg);
003200 if( p5 ){
003201 sqlite3VdbeChangeP5(v, p5);
003202 }else{
003203 sqlite3ExprCacheStore(pParse, iTable, iColumn, iReg);
003204 }
003205 return iReg;
003206 }
003207 void sqlite3ExprCodeGetColumnToReg(
003208 Parse *pParse, /* Parsing and code generating context */
003209 Table *pTab, /* Description of the table we are reading from */
003210 int iColumn, /* Index of the table column */
003211 int iTable, /* The cursor pointing to the table */
003212 int iReg /* Store results here */
003213 ){
003214 int r1 = sqlite3ExprCodeGetColumn(pParse, pTab, iColumn, iTable, iReg, 0);
003215 if( r1!=iReg ) sqlite3VdbeAddOp2(pParse->pVdbe, OP_SCopy, r1, iReg);
003216 }
003217
003218
003219 /*
003220 ** Clear all column cache entries.
003221 */
003222 void sqlite3ExprCacheClear(Parse *pParse){
003223 int i;
003224
003225 #if SQLITE_DEBUG
003226 if( pParse->db->flags & SQLITE_VdbeAddopTrace ){
003227 printf("CLEAR\n");
003228 }
003229 #endif
003230 for(i=0; i<pParse->nColCache; i++){
003231 if( pParse->aColCache[i].tempReg
003232 && pParse->nTempReg<ArraySize(pParse->aTempReg)
003233 ){
003234 pParse->aTempReg[pParse->nTempReg++] = pParse->aColCache[i].iReg;
003235 }
003236 }
003237 pParse->nColCache = 0;
003238 }
003239
003240 /*
003241 ** Record the fact that an affinity change has occurred on iCount
003242 ** registers starting with iStart.
003243 */
003244 void sqlite3ExprCacheAffinityChange(Parse *pParse, int iStart, int iCount){
003245 sqlite3ExprCacheRemove(pParse, iStart, iCount);
003246 }
003247
003248 /*
003249 ** Generate code to move content from registers iFrom...iFrom+nReg-1
003250 ** over to iTo..iTo+nReg-1. Keep the column cache up-to-date.
003251 */
003252 void sqlite3ExprCodeMove(Parse *pParse, int iFrom, int iTo, int nReg){
003253 assert( iFrom>=iTo+nReg || iFrom+nReg<=iTo );
003254 sqlite3VdbeAddOp3(pParse->pVdbe, OP_Move, iFrom, iTo, nReg);
003255 sqlite3ExprCacheRemove(pParse, iFrom, nReg);
003256 }
003257
003258 #if defined(SQLITE_DEBUG) || defined(SQLITE_COVERAGE_TEST)
003259 /*
003260 ** Return true if any register in the range iFrom..iTo (inclusive)
003261 ** is used as part of the column cache.
003262 **
003263 ** This routine is used within assert() and testcase() macros only
003264 ** and does not appear in a normal build.
003265 */
003266 static int usedAsColumnCache(Parse *pParse, int iFrom, int iTo){
003267 int i;
003268 struct yColCache *p;
003269 for(i=0, p=pParse->aColCache; i<pParse->nColCache; i++, p++){
003270 int r = p->iReg;
003271 if( r>=iFrom && r<=iTo ) return 1; /*NO_TEST*/
003272 }
003273 return 0;
003274 }
003275 #endif /* SQLITE_DEBUG || SQLITE_COVERAGE_TEST */
003276
003277
003278 /*
003279 ** Convert a scalar expression node to a TK_REGISTER referencing
003280 ** register iReg. The caller must ensure that iReg already contains
003281 ** the correct value for the expression.
003282 */
003283 static void exprToRegister(Expr *p, int iReg){
003284 p->op2 = p->op;
003285 p->op = TK_REGISTER;
003286 p->iTable = iReg;
003287 ExprClearProperty(p, EP_Skip);
003288 }
003289
003290 /*
003291 ** Evaluate an expression (either a vector or a scalar expression) and store
003292 ** the result in continguous temporary registers. Return the index of
003293 ** the first register used to store the result.
003294 **
003295 ** If the returned result register is a temporary scalar, then also write
003296 ** that register number into *piFreeable. If the returned result register
003297 ** is not a temporary or if the expression is a vector set *piFreeable
003298 ** to 0.
003299 */
003300 static int exprCodeVector(Parse *pParse, Expr *p, int *piFreeable){
003301 int iResult;
003302 int nResult = sqlite3ExprVectorSize(p);
003303 if( nResult==1 ){
003304 iResult = sqlite3ExprCodeTemp(pParse, p, piFreeable);
003305 }else{
003306 *piFreeable = 0;
003307 if( p->op==TK_SELECT ){
003308 iResult = sqlite3CodeSubselect(pParse, p, 0, 0);
003309 }else{
003310 int i;
003311 iResult = pParse->nMem+1;
003312 pParse->nMem += nResult;
003313 for(i=0; i<nResult; i++){
003314 sqlite3ExprCodeFactorable(pParse, p->x.pList->a[i].pExpr, i+iResult);
003315 }
003316 }
003317 }
003318 return iResult;
003319 }
003320
003321
003322 /*
003323 ** Generate code into the current Vdbe to evaluate the given
003324 ** expression. Attempt to store the results in register "target".
003325 ** Return the register where results are stored.
003326 **
003327 ** With this routine, there is no guarantee that results will
003328 ** be stored in target. The result might be stored in some other
003329 ** register if it is convenient to do so. The calling function
003330 ** must check the return code and move the results to the desired
003331 ** register.
003332 */
003333 int sqlite3ExprCodeTarget(Parse *pParse, Expr *pExpr, int target){
003334 Vdbe *v = pParse->pVdbe; /* The VM under construction */
003335 int op; /* The opcode being coded */
003336 int inReg = target; /* Results stored in register inReg */
003337 int regFree1 = 0; /* If non-zero free this temporary register */
003338 int regFree2 = 0; /* If non-zero free this temporary register */
003339 int r1, r2; /* Various register numbers */
003340 Expr tempX; /* Temporary expression node */
003341 int p5 = 0;
003342
003343 assert( target>0 && target<=pParse->nMem );
003344 if( v==0 ){
003345 assert( pParse->db->mallocFailed );
003346 return 0;
003347 }
003348
003349 if( pExpr==0 ){
003350 op = TK_NULL;
003351 }else{
003352 op = pExpr->op;
003353 }
003354 switch( op ){
003355 case TK_AGG_COLUMN: {
003356 AggInfo *pAggInfo = pExpr->pAggInfo;
003357 struct AggInfo_col *pCol = &pAggInfo->aCol[pExpr->iAgg];
003358 if( !pAggInfo->directMode ){
003359 assert( pCol->iMem>0 );
003360 return pCol->iMem;
003361 }else if( pAggInfo->useSortingIdx ){
003362 sqlite3VdbeAddOp3(v, OP_Column, pAggInfo->sortingIdxPTab,
003363 pCol->iSorterColumn, target);
003364 return target;
003365 }
003366 /* Otherwise, fall thru into the TK_COLUMN case */
003367 }
003368 case TK_COLUMN: {
003369 int iTab = pExpr->iTable;
003370 if( iTab<0 ){
003371 if( pParse->ckBase>0 ){
003372 /* Generating CHECK constraints or inserting into partial index */
003373 return pExpr->iColumn + pParse->ckBase;
003374 }else{
003375 /* Coding an expression that is part of an index where column names
003376 ** in the index refer to the table to which the index belongs */
003377 iTab = pParse->iSelfTab;
003378 }
003379 }
003380 return sqlite3ExprCodeGetColumn(pParse, pExpr->pTab,
003381 pExpr->iColumn, iTab, target,
003382 pExpr->op2);
003383 }
003384 case TK_INTEGER: {
003385 codeInteger(pParse, pExpr, 0, target);
003386 return target;
003387 }
003388 #ifndef SQLITE_OMIT_FLOATING_POINT
003389 case TK_FLOAT: {
003390 assert( !ExprHasProperty(pExpr, EP_IntValue) );
003391 codeReal(v, pExpr->u.zToken, 0, target);
003392 return target;
003393 }
003394 #endif
003395 case TK_STRING: {
003396 assert( !ExprHasProperty(pExpr, EP_IntValue) );
003397 sqlite3VdbeLoadString(v, target, pExpr->u.zToken);
003398 return target;
003399 }
003400 case TK_NULL: {
003401 sqlite3VdbeAddOp2(v, OP_Null, 0, target);
003402 return target;
003403 }
003404 #ifndef SQLITE_OMIT_BLOB_LITERAL
003405 case TK_BLOB: {
003406 int n;
003407 const char *z;
003408 char *zBlob;
003409 assert( !ExprHasProperty(pExpr, EP_IntValue) );
003410 assert( pExpr->u.zToken[0]=='x' || pExpr->u.zToken[0]=='X' );
003411 assert( pExpr->u.zToken[1]=='\'' );
003412 z = &pExpr->u.zToken[2];
003413 n = sqlite3Strlen30(z) - 1;
003414 assert( z[n]=='\'' );
003415 zBlob = sqlite3HexToBlob(sqlite3VdbeDb(v), z, n);
003416 sqlite3VdbeAddOp4(v, OP_Blob, n/2, target, 0, zBlob, P4_DYNAMIC);
003417 return target;
003418 }
003419 #endif
003420 case TK_VARIABLE: {
003421 assert( !ExprHasProperty(pExpr, EP_IntValue) );
003422 assert( pExpr->u.zToken!=0 );
003423 assert( pExpr->u.zToken[0]!=0 );
003424 sqlite3VdbeAddOp2(v, OP_Variable, pExpr->iColumn, target);
003425 if( pExpr->u.zToken[1]!=0 ){
003426 const char *z = sqlite3VListNumToName(pParse->pVList, pExpr->iColumn);
003427 assert( pExpr->u.zToken[0]=='?' || strcmp(pExpr->u.zToken, z)==0 );
003428 pParse->pVList[0] = 0; /* Indicate VList may no longer be enlarged */
003429 sqlite3VdbeAppendP4(v, (char*)z, P4_STATIC);
003430 }
003431 return target;
003432 }
003433 case TK_REGISTER: {
003434 return pExpr->iTable;
003435 }
003436 #ifndef SQLITE_OMIT_CAST
003437 case TK_CAST: {
003438 /* Expressions of the form: CAST(pLeft AS token) */
003439 inReg = sqlite3ExprCodeTarget(pParse, pExpr->pLeft, target);
003440 if( inReg!=target ){
003441 sqlite3VdbeAddOp2(v, OP_SCopy, inReg, target);
003442 inReg = target;
003443 }
003444 sqlite3VdbeAddOp2(v, OP_Cast, target,
003445 sqlite3AffinityType(pExpr->u.zToken, 0));
003446 testcase( usedAsColumnCache(pParse, inReg, inReg) );
003447 sqlite3ExprCacheAffinityChange(pParse, inReg, 1);
003448 return inReg;
003449 }
003450 #endif /* SQLITE_OMIT_CAST */
003451 case TK_IS:
003452 case TK_ISNOT:
003453 op = (op==TK_IS) ? TK_EQ : TK_NE;
003454 p5 = SQLITE_NULLEQ;
003455 /* fall-through */
003456 case TK_LT:
003457 case TK_LE:
003458 case TK_GT:
003459 case TK_GE:
003460 case TK_NE:
003461 case TK_EQ: {
003462 Expr *pLeft = pExpr->pLeft;
003463 if( sqlite3ExprIsVector(pLeft) ){
003464 codeVectorCompare(pParse, pExpr, target, op, p5);
003465 }else{
003466 r1 = sqlite3ExprCodeTemp(pParse, pLeft, ®Free1);
003467 r2 = sqlite3ExprCodeTemp(pParse, pExpr->pRight, ®Free2);
003468 codeCompare(pParse, pLeft, pExpr->pRight, op,
003469 r1, r2, inReg, SQLITE_STOREP2 | p5);
003470 assert(TK_LT==OP_Lt); testcase(op==OP_Lt); VdbeCoverageIf(v,op==OP_Lt);
003471 assert(TK_LE==OP_Le); testcase(op==OP_Le); VdbeCoverageIf(v,op==OP_Le);
003472 assert(TK_GT==OP_Gt); testcase(op==OP_Gt); VdbeCoverageIf(v,op==OP_Gt);
003473 assert(TK_GE==OP_Ge); testcase(op==OP_Ge); VdbeCoverageIf(v,op==OP_Ge);
003474 assert(TK_EQ==OP_Eq); testcase(op==OP_Eq); VdbeCoverageIf(v,op==OP_Eq);
003475 assert(TK_NE==OP_Ne); testcase(op==OP_Ne); VdbeCoverageIf(v,op==OP_Ne);
003476 testcase( regFree1==0 );
003477 testcase( regFree2==0 );
003478 }
003479 break;
003480 }
003481 case TK_AND:
003482 case TK_OR:
003483 case TK_PLUS:
003484 case TK_STAR:
003485 case TK_MINUS:
003486 case TK_REM:
003487 case TK_BITAND:
003488 case TK_BITOR:
003489 case TK_SLASH:
003490 case TK_LSHIFT:
003491 case TK_RSHIFT:
003492 case TK_CONCAT: {
003493 assert( TK_AND==OP_And ); testcase( op==TK_AND );
003494 assert( TK_OR==OP_Or ); testcase( op==TK_OR );
003495 assert( TK_PLUS==OP_Add ); testcase( op==TK_PLUS );
003496 assert( TK_MINUS==OP_Subtract ); testcase( op==TK_MINUS );
003497 assert( TK_REM==OP_Remainder ); testcase( op==TK_REM );
003498 assert( TK_BITAND==OP_BitAnd ); testcase( op==TK_BITAND );
003499 assert( TK_BITOR==OP_BitOr ); testcase( op==TK_BITOR );
003500 assert( TK_SLASH==OP_Divide ); testcase( op==TK_SLASH );
003501 assert( TK_LSHIFT==OP_ShiftLeft ); testcase( op==TK_LSHIFT );
003502 assert( TK_RSHIFT==OP_ShiftRight ); testcase( op==TK_RSHIFT );
003503 assert( TK_CONCAT==OP_Concat ); testcase( op==TK_CONCAT );
003504 r1 = sqlite3ExprCodeTemp(pParse, pExpr->pLeft, ®Free1);
003505 r2 = sqlite3ExprCodeTemp(pParse, pExpr->pRight, ®Free2);
003506 sqlite3VdbeAddOp3(v, op, r2, r1, target);
003507 testcase( regFree1==0 );
003508 testcase( regFree2==0 );
003509 break;
003510 }
003511 case TK_UMINUS: {
003512 Expr *pLeft = pExpr->pLeft;
003513 assert( pLeft );
003514 if( pLeft->op==TK_INTEGER ){
003515 codeInteger(pParse, pLeft, 1, target);
003516 return target;
003517 #ifndef SQLITE_OMIT_FLOATING_POINT
003518 }else if( pLeft->op==TK_FLOAT ){
003519 assert( !ExprHasProperty(pExpr, EP_IntValue) );
003520 codeReal(v, pLeft->u.zToken, 1, target);
003521 return target;
003522 #endif
003523 }else{
003524 tempX.op = TK_INTEGER;
003525 tempX.flags = EP_IntValue|EP_TokenOnly;
003526 tempX.u.iValue = 0;
003527 r1 = sqlite3ExprCodeTemp(pParse, &tempX, ®Free1);
003528 r2 = sqlite3ExprCodeTemp(pParse, pExpr->pLeft, ®Free2);
003529 sqlite3VdbeAddOp3(v, OP_Subtract, r2, r1, target);
003530 testcase( regFree2==0 );
003531 }
003532 break;
003533 }
003534 case TK_BITNOT:
003535 case TK_NOT: {
003536 assert( TK_BITNOT==OP_BitNot ); testcase( op==TK_BITNOT );
003537 assert( TK_NOT==OP_Not ); testcase( op==TK_NOT );
003538 r1 = sqlite3ExprCodeTemp(pParse, pExpr->pLeft, ®Free1);
003539 testcase( regFree1==0 );
003540 sqlite3VdbeAddOp2(v, op, r1, inReg);
003541 break;
003542 }
003543 case TK_ISNULL:
003544 case TK_NOTNULL: {
003545 int addr;
003546 assert( TK_ISNULL==OP_IsNull ); testcase( op==TK_ISNULL );
003547 assert( TK_NOTNULL==OP_NotNull ); testcase( op==TK_NOTNULL );
003548 sqlite3VdbeAddOp2(v, OP_Integer, 1, target);
003549 r1 = sqlite3ExprCodeTemp(pParse, pExpr->pLeft, ®Free1);
003550 testcase( regFree1==0 );
003551 addr = sqlite3VdbeAddOp1(v, op, r1);
003552 VdbeCoverageIf(v, op==TK_ISNULL);
003553 VdbeCoverageIf(v, op==TK_NOTNULL);
003554 sqlite3VdbeAddOp2(v, OP_Integer, 0, target);
003555 sqlite3VdbeJumpHere(v, addr);
003556 break;
003557 }
003558 case TK_AGG_FUNCTION: {
003559 AggInfo *pInfo = pExpr->pAggInfo;
003560 if( pInfo==0 ){
003561 assert( !ExprHasProperty(pExpr, EP_IntValue) );
003562 sqlite3ErrorMsg(pParse, "misuse of aggregate: %s()", pExpr->u.zToken);
003563 }else{
003564 return pInfo->aFunc[pExpr->iAgg].iMem;
003565 }
003566 break;
003567 }
003568 case TK_FUNCTION: {
003569 ExprList *pFarg; /* List of function arguments */
003570 int nFarg; /* Number of function arguments */
003571 FuncDef *pDef; /* The function definition object */
003572 const char *zId; /* The function name */
003573 u32 constMask = 0; /* Mask of function arguments that are constant */
003574 int i; /* Loop counter */
003575 sqlite3 *db = pParse->db; /* The database connection */
003576 u8 enc = ENC(db); /* The text encoding used by this database */
003577 CollSeq *pColl = 0; /* A collating sequence */
003578
003579 assert( !ExprHasProperty(pExpr, EP_xIsSelect) );
003580 if( ExprHasProperty(pExpr, EP_TokenOnly) ){
003581 pFarg = 0;
003582 }else{
003583 pFarg = pExpr->x.pList;
003584 }
003585 nFarg = pFarg ? pFarg->nExpr : 0;
003586 assert( !ExprHasProperty(pExpr, EP_IntValue) );
003587 zId = pExpr->u.zToken;
003588 pDef = sqlite3FindFunction(db, zId, nFarg, enc, 0);
003589 #ifdef SQLITE_ENABLE_UNKNOWN_SQL_FUNCTION
003590 if( pDef==0 && pParse->explain ){
003591 pDef = sqlite3FindFunction(db, "unknown", nFarg, enc, 0);
003592 }
003593 #endif
003594 if( pDef==0 || pDef->xFinalize!=0 ){
003595 sqlite3ErrorMsg(pParse, "unknown function: %s()", zId);
003596 break;
003597 }
003598
003599 /* Attempt a direct implementation of the built-in COALESCE() and
003600 ** IFNULL() functions. This avoids unnecessary evaluation of
003601 ** arguments past the first non-NULL argument.
003602 */
003603 if( pDef->funcFlags & SQLITE_FUNC_COALESCE ){
003604 int endCoalesce = sqlite3VdbeMakeLabel(v);
003605 assert( nFarg>=2 );
003606 sqlite3ExprCode(pParse, pFarg->a[0].pExpr, target);
003607 for(i=1; i<nFarg; i++){
003608 sqlite3VdbeAddOp2(v, OP_NotNull, target, endCoalesce);
003609 VdbeCoverage(v);
003610 sqlite3ExprCacheRemove(pParse, target, 1);
003611 sqlite3ExprCachePush(pParse);
003612 sqlite3ExprCode(pParse, pFarg->a[i].pExpr, target);
003613 sqlite3ExprCachePop(pParse);
003614 }
003615 sqlite3VdbeResolveLabel(v, endCoalesce);
003616 break;
003617 }
003618
003619 /* The UNLIKELY() function is a no-op. The result is the value
003620 ** of the first argument.
003621 */
003622 if( pDef->funcFlags & SQLITE_FUNC_UNLIKELY ){
003623 assert( nFarg>=1 );
003624 return sqlite3ExprCodeTarget(pParse, pFarg->a[0].pExpr, target);
003625 }
003626
003627 for(i=0; i<nFarg; i++){
003628 if( i<32 && sqlite3ExprIsConstant(pFarg->a[i].pExpr) ){
003629 testcase( i==31 );
003630 constMask |= MASKBIT32(i);
003631 }
003632 if( (pDef->funcFlags & SQLITE_FUNC_NEEDCOLL)!=0 && !pColl ){
003633 pColl = sqlite3ExprCollSeq(pParse, pFarg->a[i].pExpr);
003634 }
003635 }
003636 if( pFarg ){
003637 if( constMask ){
003638 r1 = pParse->nMem+1;
003639 pParse->nMem += nFarg;
003640 }else{
003641 r1 = sqlite3GetTempRange(pParse, nFarg);
003642 }
003643
003644 /* For length() and typeof() functions with a column argument,
003645 ** set the P5 parameter to the OP_Column opcode to OPFLAG_LENGTHARG
003646 ** or OPFLAG_TYPEOFARG respectively, to avoid unnecessary data
003647 ** loading.
003648 */
003649 if( (pDef->funcFlags & (SQLITE_FUNC_LENGTH|SQLITE_FUNC_TYPEOF))!=0 ){
003650 u8 exprOp;
003651 assert( nFarg==1 );
003652 assert( pFarg->a[0].pExpr!=0 );
003653 exprOp = pFarg->a[0].pExpr->op;
003654 if( exprOp==TK_COLUMN || exprOp==TK_AGG_COLUMN ){
003655 assert( SQLITE_FUNC_LENGTH==OPFLAG_LENGTHARG );
003656 assert( SQLITE_FUNC_TYPEOF==OPFLAG_TYPEOFARG );
003657 testcase( pDef->funcFlags & OPFLAG_LENGTHARG );
003658 pFarg->a[0].pExpr->op2 =
003659 pDef->funcFlags & (OPFLAG_LENGTHARG|OPFLAG_TYPEOFARG);
003660 }
003661 }
003662
003663 sqlite3ExprCachePush(pParse); /* Ticket 2ea2425d34be */
003664 sqlite3ExprCodeExprList(pParse, pFarg, r1, 0,
003665 SQLITE_ECEL_DUP|SQLITE_ECEL_FACTOR);
003666 sqlite3ExprCachePop(pParse); /* Ticket 2ea2425d34be */
003667 }else{
003668 r1 = 0;
003669 }
003670 #ifndef SQLITE_OMIT_VIRTUALTABLE
003671 /* Possibly overload the function if the first argument is
003672 ** a virtual table column.
003673 **
003674 ** For infix functions (LIKE, GLOB, REGEXP, and MATCH) use the
003675 ** second argument, not the first, as the argument to test to
003676 ** see if it is a column in a virtual table. This is done because
003677 ** the left operand of infix functions (the operand we want to
003678 ** control overloading) ends up as the second argument to the
003679 ** function. The expression "A glob B" is equivalent to
003680 ** "glob(B,A). We want to use the A in "A glob B" to test
003681 ** for function overloading. But we use the B term in "glob(B,A)".
003682 */
003683 if( nFarg>=2 && (pExpr->flags & EP_InfixFunc) ){
003684 pDef = sqlite3VtabOverloadFunction(db, pDef, nFarg, pFarg->a[1].pExpr);
003685 }else if( nFarg>0 ){
003686 pDef = sqlite3VtabOverloadFunction(db, pDef, nFarg, pFarg->a[0].pExpr);
003687 }
003688 #endif
003689 if( pDef->funcFlags & SQLITE_FUNC_NEEDCOLL ){
003690 if( !pColl ) pColl = db->pDfltColl;
003691 sqlite3VdbeAddOp4(v, OP_CollSeq, 0, 0, 0, (char *)pColl, P4_COLLSEQ);
003692 }
003693 sqlite3VdbeAddOp4(v, OP_Function0, constMask, r1, target,
003694 (char*)pDef, P4_FUNCDEF);
003695 sqlite3VdbeChangeP5(v, (u8)nFarg);
003696 if( nFarg && constMask==0 ){
003697 sqlite3ReleaseTempRange(pParse, r1, nFarg);
003698 }
003699 return target;
003700 }
003701 #ifndef SQLITE_OMIT_SUBQUERY
003702 case TK_EXISTS:
003703 case TK_SELECT: {
003704 int nCol;
003705 testcase( op==TK_EXISTS );
003706 testcase( op==TK_SELECT );
003707 if( op==TK_SELECT && (nCol = pExpr->x.pSelect->pEList->nExpr)!=1 ){
003708 sqlite3SubselectError(pParse, nCol, 1);
003709 }else{
003710 return sqlite3CodeSubselect(pParse, pExpr, 0, 0);
003711 }
003712 break;
003713 }
003714 case TK_SELECT_COLUMN: {
003715 if( pExpr->pLeft->iTable==0 ){
003716 pExpr->pLeft->iTable = sqlite3CodeSubselect(pParse, pExpr->pLeft, 0, 0);
003717 }
003718 return pExpr->pLeft->iTable + pExpr->iColumn;
003719 }
003720 case TK_IN: {
003721 int destIfFalse = sqlite3VdbeMakeLabel(v);
003722 int destIfNull = sqlite3VdbeMakeLabel(v);
003723 sqlite3VdbeAddOp2(v, OP_Null, 0, target);
003724 sqlite3ExprCodeIN(pParse, pExpr, destIfFalse, destIfNull);
003725 sqlite3VdbeAddOp2(v, OP_Integer, 1, target);
003726 sqlite3VdbeResolveLabel(v, destIfFalse);
003727 sqlite3VdbeAddOp2(v, OP_AddImm, target, 0);
003728 sqlite3VdbeResolveLabel(v, destIfNull);
003729 return target;
003730 }
003731 #endif /* SQLITE_OMIT_SUBQUERY */
003732
003733
003734 /*
003735 ** x BETWEEN y AND z
003736 **
003737 ** This is equivalent to
003738 **
003739 ** x>=y AND x<=z
003740 **
003741 ** X is stored in pExpr->pLeft.
003742 ** Y is stored in pExpr->pList->a[0].pExpr.
003743 ** Z is stored in pExpr->pList->a[1].pExpr.
003744 */
003745 case TK_BETWEEN: {
003746 exprCodeBetween(pParse, pExpr, target, 0, 0);
003747 return target;
003748 }
003749 case TK_SPAN:
003750 case TK_COLLATE:
003751 case TK_UPLUS: {
003752 return sqlite3ExprCodeTarget(pParse, pExpr->pLeft, target);
003753 }
003754
003755 case TK_TRIGGER: {
003756 /* If the opcode is TK_TRIGGER, then the expression is a reference
003757 ** to a column in the new.* or old.* pseudo-tables available to
003758 ** trigger programs. In this case Expr.iTable is set to 1 for the
003759 ** new.* pseudo-table, or 0 for the old.* pseudo-table. Expr.iColumn
003760 ** is set to the column of the pseudo-table to read, or to -1 to
003761 ** read the rowid field.
003762 **
003763 ** The expression is implemented using an OP_Param opcode. The p1
003764 ** parameter is set to 0 for an old.rowid reference, or to (i+1)
003765 ** to reference another column of the old.* pseudo-table, where
003766 ** i is the index of the column. For a new.rowid reference, p1 is
003767 ** set to (n+1), where n is the number of columns in each pseudo-table.
003768 ** For a reference to any other column in the new.* pseudo-table, p1
003769 ** is set to (n+2+i), where n and i are as defined previously. For
003770 ** example, if the table on which triggers are being fired is
003771 ** declared as:
003772 **
003773 ** CREATE TABLE t1(a, b);
003774 **
003775 ** Then p1 is interpreted as follows:
003776 **
003777 ** p1==0 -> old.rowid p1==3 -> new.rowid
003778 ** p1==1 -> old.a p1==4 -> new.a
003779 ** p1==2 -> old.b p1==5 -> new.b
003780 */
003781 Table *pTab = pExpr->pTab;
003782 int p1 = pExpr->iTable * (pTab->nCol+1) + 1 + pExpr->iColumn;
003783
003784 assert( pExpr->iTable==0 || pExpr->iTable==1 );
003785 assert( pExpr->iColumn>=-1 && pExpr->iColumn<pTab->nCol );
003786 assert( pTab->iPKey<0 || pExpr->iColumn!=pTab->iPKey );
003787 assert( p1>=0 && p1<(pTab->nCol*2+2) );
003788
003789 sqlite3VdbeAddOp2(v, OP_Param, p1, target);
003790 VdbeComment((v, "%s.%s -> $%d",
003791 (pExpr->iTable ? "new" : "old"),
003792 (pExpr->iColumn<0 ? "rowid" : pExpr->pTab->aCol[pExpr->iColumn].zName),
003793 target
003794 ));
003795
003796 #ifndef SQLITE_OMIT_FLOATING_POINT
003797 /* If the column has REAL affinity, it may currently be stored as an
003798 ** integer. Use OP_RealAffinity to make sure it is really real.
003799 **
003800 ** EVIDENCE-OF: R-60985-57662 SQLite will convert the value back to
003801 ** floating point when extracting it from the record. */
003802 if( pExpr->iColumn>=0
003803 && pTab->aCol[pExpr->iColumn].affinity==SQLITE_AFF_REAL
003804 ){
003805 sqlite3VdbeAddOp1(v, OP_RealAffinity, target);
003806 }
003807 #endif
003808 break;
003809 }
003810
003811 case TK_VECTOR: {
003812 sqlite3ErrorMsg(pParse, "row value misused");
003813 break;
003814 }
003815
003816 /*
003817 ** Form A:
003818 ** CASE x WHEN e1 THEN r1 WHEN e2 THEN r2 ... WHEN eN THEN rN ELSE y END
003819 **
003820 ** Form B:
003821 ** CASE WHEN e1 THEN r1 WHEN e2 THEN r2 ... WHEN eN THEN rN ELSE y END
003822 **
003823 ** Form A is can be transformed into the equivalent form B as follows:
003824 ** CASE WHEN x=e1 THEN r1 WHEN x=e2 THEN r2 ...
003825 ** WHEN x=eN THEN rN ELSE y END
003826 **
003827 ** X (if it exists) is in pExpr->pLeft.
003828 ** Y is in the last element of pExpr->x.pList if pExpr->x.pList->nExpr is
003829 ** odd. The Y is also optional. If the number of elements in x.pList
003830 ** is even, then Y is omitted and the "otherwise" result is NULL.
003831 ** Ei is in pExpr->pList->a[i*2] and Ri is pExpr->pList->a[i*2+1].
003832 **
003833 ** The result of the expression is the Ri for the first matching Ei,
003834 ** or if there is no matching Ei, the ELSE term Y, or if there is
003835 ** no ELSE term, NULL.
003836 */
003837 default: assert( op==TK_CASE ); {
003838 int endLabel; /* GOTO label for end of CASE stmt */
003839 int nextCase; /* GOTO label for next WHEN clause */
003840 int nExpr; /* 2x number of WHEN terms */
003841 int i; /* Loop counter */
003842 ExprList *pEList; /* List of WHEN terms */
003843 struct ExprList_item *aListelem; /* Array of WHEN terms */
003844 Expr opCompare; /* The X==Ei expression */
003845 Expr *pX; /* The X expression */
003846 Expr *pTest = 0; /* X==Ei (form A) or just Ei (form B) */
003847 VVA_ONLY( int iCacheLevel = pParse->iCacheLevel; )
003848
003849 assert( !ExprHasProperty(pExpr, EP_xIsSelect) && pExpr->x.pList );
003850 assert(pExpr->x.pList->nExpr > 0);
003851 pEList = pExpr->x.pList;
003852 aListelem = pEList->a;
003853 nExpr = pEList->nExpr;
003854 endLabel = sqlite3VdbeMakeLabel(v);
003855 if( (pX = pExpr->pLeft)!=0 ){
003856 tempX = *pX;
003857 testcase( pX->op==TK_COLUMN );
003858 exprToRegister(&tempX, exprCodeVector(pParse, &tempX, ®Free1));
003859 testcase( regFree1==0 );
003860 memset(&opCompare, 0, sizeof(opCompare));
003861 opCompare.op = TK_EQ;
003862 opCompare.pLeft = &tempX;
003863 pTest = &opCompare;
003864 /* Ticket b351d95f9cd5ef17e9d9dbae18f5ca8611190001:
003865 ** The value in regFree1 might get SCopy-ed into the file result.
003866 ** So make sure that the regFree1 register is not reused for other
003867 ** purposes and possibly overwritten. */
003868 regFree1 = 0;
003869 }
003870 for(i=0; i<nExpr-1; i=i+2){
003871 sqlite3ExprCachePush(pParse);
003872 if( pX ){
003873 assert( pTest!=0 );
003874 opCompare.pRight = aListelem[i].pExpr;
003875 }else{
003876 pTest = aListelem[i].pExpr;
003877 }
003878 nextCase = sqlite3VdbeMakeLabel(v);
003879 testcase( pTest->op==TK_COLUMN );
003880 sqlite3ExprIfFalse(pParse, pTest, nextCase, SQLITE_JUMPIFNULL);
003881 testcase( aListelem[i+1].pExpr->op==TK_COLUMN );
003882 sqlite3ExprCode(pParse, aListelem[i+1].pExpr, target);
003883 sqlite3VdbeGoto(v, endLabel);
003884 sqlite3ExprCachePop(pParse);
003885 sqlite3VdbeResolveLabel(v, nextCase);
003886 }
003887 if( (nExpr&1)!=0 ){
003888 sqlite3ExprCachePush(pParse);
003889 sqlite3ExprCode(pParse, pEList->a[nExpr-1].pExpr, target);
003890 sqlite3ExprCachePop(pParse);
003891 }else{
003892 sqlite3VdbeAddOp2(v, OP_Null, 0, target);
003893 }
003894 assert( pParse->db->mallocFailed || pParse->nErr>0
003895 || pParse->iCacheLevel==iCacheLevel );
003896 sqlite3VdbeResolveLabel(v, endLabel);
003897 break;
003898 }
003899 #ifndef SQLITE_OMIT_TRIGGER
003900 case TK_RAISE: {
003901 assert( pExpr->affinity==OE_Rollback
003902 || pExpr->affinity==OE_Abort
003903 || pExpr->affinity==OE_Fail
003904 || pExpr->affinity==OE_Ignore
003905 );
003906 if( !pParse->pTriggerTab ){
003907 sqlite3ErrorMsg(pParse,
003908 "RAISE() may only be used within a trigger-program");
003909 return 0;
003910 }
003911 if( pExpr->affinity==OE_Abort ){
003912 sqlite3MayAbort(pParse);
003913 }
003914 assert( !ExprHasProperty(pExpr, EP_IntValue) );
003915 if( pExpr->affinity==OE_Ignore ){
003916 sqlite3VdbeAddOp4(
003917 v, OP_Halt, SQLITE_OK, OE_Ignore, 0, pExpr->u.zToken,0);
003918 VdbeCoverage(v);
003919 }else{
003920 sqlite3HaltConstraint(pParse, SQLITE_CONSTRAINT_TRIGGER,
003921 pExpr->affinity, pExpr->u.zToken, 0, 0);
003922 }
003923
003924 break;
003925 }
003926 #endif
003927 }
003928 sqlite3ReleaseTempReg(pParse, regFree1);
003929 sqlite3ReleaseTempReg(pParse, regFree2);
003930 return inReg;
003931 }
003932
003933 /*
003934 ** Factor out the code of the given expression to initialization time.
003935 */
003936 void sqlite3ExprCodeAtInit(
003937 Parse *pParse, /* Parsing context */
003938 Expr *pExpr, /* The expression to code when the VDBE initializes */
003939 int regDest, /* Store the value in this register */
003940 u8 reusable /* True if this expression is reusable */
003941 ){
003942 ExprList *p;
003943 assert( ConstFactorOk(pParse) );
003944 p = pParse->pConstExpr;
003945 pExpr = sqlite3ExprDup(pParse->db, pExpr, 0);
003946 p = sqlite3ExprListAppend(pParse, p, pExpr);
003947 if( p ){
003948 struct ExprList_item *pItem = &p->a[p->nExpr-1];
003949 pItem->u.iConstExprReg = regDest;
003950 pItem->reusable = reusable;
003951 }
003952 pParse->pConstExpr = p;
003953 }
003954
003955 /*
003956 ** Generate code to evaluate an expression and store the results
003957 ** into a register. Return the register number where the results
003958 ** are stored.
003959 **
003960 ** If the register is a temporary register that can be deallocated,
003961 ** then write its number into *pReg. If the result register is not
003962 ** a temporary, then set *pReg to zero.
003963 **
003964 ** If pExpr is a constant, then this routine might generate this
003965 ** code to fill the register in the initialization section of the
003966 ** VDBE program, in order to factor it out of the evaluation loop.
003967 */
003968 int sqlite3ExprCodeTemp(Parse *pParse, Expr *pExpr, int *pReg){
003969 int r2;
003970 pExpr = sqlite3ExprSkipCollate(pExpr);
003971 if( ConstFactorOk(pParse)
003972 && pExpr->op!=TK_REGISTER
003973 && sqlite3ExprIsConstantNotJoin(pExpr)
003974 ){
003975 ExprList *p = pParse->pConstExpr;
003976 int i;
003977 *pReg = 0;
003978 if( p ){
003979 struct ExprList_item *pItem;
003980 for(pItem=p->a, i=p->nExpr; i>0; pItem++, i--){
003981 if( pItem->reusable && sqlite3ExprCompare(pItem->pExpr,pExpr,-1)==0 ){
003982 return pItem->u.iConstExprReg;
003983 }
003984 }
003985 }
003986 r2 = ++pParse->nMem;
003987 sqlite3ExprCodeAtInit(pParse, pExpr, r2, 1);
003988 }else{
003989 int r1 = sqlite3GetTempReg(pParse);
003990 r2 = sqlite3ExprCodeTarget(pParse, pExpr, r1);
003991 if( r2==r1 ){
003992 *pReg = r1;
003993 }else{
003994 sqlite3ReleaseTempReg(pParse, r1);
003995 *pReg = 0;
003996 }
003997 }
003998 return r2;
003999 }
004000
004001 /*
004002 ** Generate code that will evaluate expression pExpr and store the
004003 ** results in register target. The results are guaranteed to appear
004004 ** in register target.
004005 */
004006 void sqlite3ExprCode(Parse *pParse, Expr *pExpr, int target){
004007 int inReg;
004008
004009 assert( target>0 && target<=pParse->nMem );
004010 if( pExpr && pExpr->op==TK_REGISTER ){
004011 sqlite3VdbeAddOp2(pParse->pVdbe, OP_Copy, pExpr->iTable, target);
004012 }else{
004013 inReg = sqlite3ExprCodeTarget(pParse, pExpr, target);
004014 assert( pParse->pVdbe!=0 || pParse->db->mallocFailed );
004015 if( inReg!=target && pParse->pVdbe ){
004016 sqlite3VdbeAddOp2(pParse->pVdbe, OP_SCopy, inReg, target);
004017 }
004018 }
004019 }
004020
004021 /*
004022 ** Make a transient copy of expression pExpr and then code it using
004023 ** sqlite3ExprCode(). This routine works just like sqlite3ExprCode()
004024 ** except that the input expression is guaranteed to be unchanged.
004025 */
004026 void sqlite3ExprCodeCopy(Parse *pParse, Expr *pExpr, int target){
004027 sqlite3 *db = pParse->db;
004028 pExpr = sqlite3ExprDup(db, pExpr, 0);
004029 if( !db->mallocFailed ) sqlite3ExprCode(pParse, pExpr, target);
004030 sqlite3ExprDelete(db, pExpr);
004031 }
004032
004033 /*
004034 ** Generate code that will evaluate expression pExpr and store the
004035 ** results in register target. The results are guaranteed to appear
004036 ** in register target. If the expression is constant, then this routine
004037 ** might choose to code the expression at initialization time.
004038 */
004039 void sqlite3ExprCodeFactorable(Parse *pParse, Expr *pExpr, int target){
004040 if( pParse->okConstFactor && sqlite3ExprIsConstant(pExpr) ){
004041 sqlite3ExprCodeAtInit(pParse, pExpr, target, 0);
004042 }else{
004043 sqlite3ExprCode(pParse, pExpr, target);
004044 }
004045 }
004046
004047 /*
004048 ** Generate code that evaluates the given expression and puts the result
004049 ** in register target.
004050 **
004051 ** Also make a copy of the expression results into another "cache" register
004052 ** and modify the expression so that the next time it is evaluated,
004053 ** the result is a copy of the cache register.
004054 **
004055 ** This routine is used for expressions that are used multiple
004056 ** times. They are evaluated once and the results of the expression
004057 ** are reused.
004058 */
004059 void sqlite3ExprCodeAndCache(Parse *pParse, Expr *pExpr, int target){
004060 Vdbe *v = pParse->pVdbe;
004061 int iMem;
004062
004063 assert( target>0 );
004064 assert( pExpr->op!=TK_REGISTER );
004065 sqlite3ExprCode(pParse, pExpr, target);
004066 iMem = ++pParse->nMem;
004067 sqlite3VdbeAddOp2(v, OP_Copy, target, iMem);
004068 exprToRegister(pExpr, iMem);
004069 }
004070
004071 /*
004072 ** Generate code that pushes the value of every element of the given
004073 ** expression list into a sequence of registers beginning at target.
004074 **
004075 ** Return the number of elements evaluated.
004076 **
004077 ** The SQLITE_ECEL_DUP flag prevents the arguments from being
004078 ** filled using OP_SCopy. OP_Copy must be used instead.
004079 **
004080 ** The SQLITE_ECEL_FACTOR argument allows constant arguments to be
004081 ** factored out into initialization code.
004082 **
004083 ** The SQLITE_ECEL_REF flag means that expressions in the list with
004084 ** ExprList.a[].u.x.iOrderByCol>0 have already been evaluated and stored
004085 ** in registers at srcReg, and so the value can be copied from there.
004086 */
004087 int sqlite3ExprCodeExprList(
004088 Parse *pParse, /* Parsing context */
004089 ExprList *pList, /* The expression list to be coded */
004090 int target, /* Where to write results */
004091 int srcReg, /* Source registers if SQLITE_ECEL_REF */
004092 u8 flags /* SQLITE_ECEL_* flags */
004093 ){
004094 struct ExprList_item *pItem;
004095 int i, j, n;
004096 u8 copyOp = (flags & SQLITE_ECEL_DUP) ? OP_Copy : OP_SCopy;
004097 Vdbe *v = pParse->pVdbe;
004098 assert( pList!=0 );
004099 assert( target>0 );
004100 assert( pParse->pVdbe!=0 ); /* Never gets this far otherwise */
004101 n = pList->nExpr;
004102 if( !ConstFactorOk(pParse) ) flags &= ~SQLITE_ECEL_FACTOR;
004103 for(pItem=pList->a, i=0; i<n; i++, pItem++){
004104 Expr *pExpr = pItem->pExpr;
004105 if( (flags & SQLITE_ECEL_REF)!=0 && (j = pItem->u.x.iOrderByCol)>0 ){
004106 if( flags & SQLITE_ECEL_OMITREF ){
004107 i--;
004108 n--;
004109 }else{
004110 sqlite3VdbeAddOp2(v, copyOp, j+srcReg-1, target+i);
004111 }
004112 }else if( (flags & SQLITE_ECEL_FACTOR)!=0 && sqlite3ExprIsConstant(pExpr) ){
004113 sqlite3ExprCodeAtInit(pParse, pExpr, target+i, 0);
004114 }else{
004115 int inReg = sqlite3ExprCodeTarget(pParse, pExpr, target+i);
004116 if( inReg!=target+i ){
004117 VdbeOp *pOp;
004118 if( copyOp==OP_Copy
004119 && (pOp=sqlite3VdbeGetOp(v, -1))->opcode==OP_Copy
004120 && pOp->p1+pOp->p3+1==inReg
004121 && pOp->p2+pOp->p3+1==target+i
004122 ){
004123 pOp->p3++;
004124 }else{
004125 sqlite3VdbeAddOp2(v, copyOp, inReg, target+i);
004126 }
004127 }
004128 }
004129 }
004130 return n;
004131 }
004132
004133 /*
004134 ** Generate code for a BETWEEN operator.
004135 **
004136 ** x BETWEEN y AND z
004137 **
004138 ** The above is equivalent to
004139 **
004140 ** x>=y AND x<=z
004141 **
004142 ** Code it as such, taking care to do the common subexpression
004143 ** elimination of x.
004144 **
004145 ** The xJumpIf parameter determines details:
004146 **
004147 ** NULL: Store the boolean result in reg[dest]
004148 ** sqlite3ExprIfTrue: Jump to dest if true
004149 ** sqlite3ExprIfFalse: Jump to dest if false
004150 **
004151 ** The jumpIfNull parameter is ignored if xJumpIf is NULL.
004152 */
004153 static void exprCodeBetween(
004154 Parse *pParse, /* Parsing and code generating context */
004155 Expr *pExpr, /* The BETWEEN expression */
004156 int dest, /* Jump destination or storage location */
004157 void (*xJump)(Parse*,Expr*,int,int), /* Action to take */
004158 int jumpIfNull /* Take the jump if the BETWEEN is NULL */
004159 ){
004160 Expr exprAnd; /* The AND operator in x>=y AND x<=z */
004161 Expr compLeft; /* The x>=y term */
004162 Expr compRight; /* The x<=z term */
004163 Expr exprX; /* The x subexpression */
004164 int regFree1 = 0; /* Temporary use register */
004165
004166
004167 memset(&compLeft, 0, sizeof(Expr));
004168 memset(&compRight, 0, sizeof(Expr));
004169 memset(&exprAnd, 0, sizeof(Expr));
004170
004171 assert( !ExprHasProperty(pExpr, EP_xIsSelect) );
004172 exprX = *pExpr->pLeft;
004173 exprAnd.op = TK_AND;
004174 exprAnd.pLeft = &compLeft;
004175 exprAnd.pRight = &compRight;
004176 compLeft.op = TK_GE;
004177 compLeft.pLeft = &exprX;
004178 compLeft.pRight = pExpr->x.pList->a[0].pExpr;
004179 compRight.op = TK_LE;
004180 compRight.pLeft = &exprX;
004181 compRight.pRight = pExpr->x.pList->a[1].pExpr;
004182 exprToRegister(&exprX, exprCodeVector(pParse, &exprX, ®Free1));
004183 if( xJump ){
004184 xJump(pParse, &exprAnd, dest, jumpIfNull);
004185 }else{
004186 /* Mark the expression is being from the ON or USING clause of a join
004187 ** so that the sqlite3ExprCodeTarget() routine will not attempt to move
004188 ** it into the Parse.pConstExpr list. We should use a new bit for this,
004189 ** for clarity, but we are out of bits in the Expr.flags field so we
004190 ** have to reuse the EP_FromJoin bit. Bummer. */
004191 exprX.flags |= EP_FromJoin;
004192 sqlite3ExprCodeTarget(pParse, &exprAnd, dest);
004193 }
004194 sqlite3ReleaseTempReg(pParse, regFree1);
004195
004196 /* Ensure adequate test coverage */
004197 testcase( xJump==sqlite3ExprIfTrue && jumpIfNull==0 && regFree1==0 );
004198 testcase( xJump==sqlite3ExprIfTrue && jumpIfNull==0 && regFree1!=0 );
004199 testcase( xJump==sqlite3ExprIfTrue && jumpIfNull!=0 && regFree1==0 );
004200 testcase( xJump==sqlite3ExprIfTrue && jumpIfNull!=0 && regFree1!=0 );
004201 testcase( xJump==sqlite3ExprIfFalse && jumpIfNull==0 && regFree1==0 );
004202 testcase( xJump==sqlite3ExprIfFalse && jumpIfNull==0 && regFree1!=0 );
004203 testcase( xJump==sqlite3ExprIfFalse && jumpIfNull!=0 && regFree1==0 );
004204 testcase( xJump==sqlite3ExprIfFalse && jumpIfNull!=0 && regFree1!=0 );
004205 testcase( xJump==0 );
004206 }
004207
004208 /*
004209 ** Generate code for a boolean expression such that a jump is made
004210 ** to the label "dest" if the expression is true but execution
004211 ** continues straight thru if the expression is false.
004212 **
004213 ** If the expression evaluates to NULL (neither true nor false), then
004214 ** take the jump if the jumpIfNull flag is SQLITE_JUMPIFNULL.
004215 **
004216 ** This code depends on the fact that certain token values (ex: TK_EQ)
004217 ** are the same as opcode values (ex: OP_Eq) that implement the corresponding
004218 ** operation. Special comments in vdbe.c and the mkopcodeh.awk script in
004219 ** the make process cause these values to align. Assert()s in the code
004220 ** below verify that the numbers are aligned correctly.
004221 */
004222 void sqlite3ExprIfTrue(Parse *pParse, Expr *pExpr, int dest, int jumpIfNull){
004223 Vdbe *v = pParse->pVdbe;
004224 int op = 0;
004225 int regFree1 = 0;
004226 int regFree2 = 0;
004227 int r1, r2;
004228
004229 assert( jumpIfNull==SQLITE_JUMPIFNULL || jumpIfNull==0 );
004230 if( NEVER(v==0) ) return; /* Existence of VDBE checked by caller */
004231 if( NEVER(pExpr==0) ) return; /* No way this can happen */
004232 op = pExpr->op;
004233 switch( op ){
004234 case TK_AND: {
004235 int d2 = sqlite3VdbeMakeLabel(v);
004236 testcase( jumpIfNull==0 );
004237 sqlite3ExprIfFalse(pParse, pExpr->pLeft, d2,jumpIfNull^SQLITE_JUMPIFNULL);
004238 sqlite3ExprCachePush(pParse);
004239 sqlite3ExprIfTrue(pParse, pExpr->pRight, dest, jumpIfNull);
004240 sqlite3VdbeResolveLabel(v, d2);
004241 sqlite3ExprCachePop(pParse);
004242 break;
004243 }
004244 case TK_OR: {
004245 testcase( jumpIfNull==0 );
004246 sqlite3ExprIfTrue(pParse, pExpr->pLeft, dest, jumpIfNull);
004247 sqlite3ExprCachePush(pParse);
004248 sqlite3ExprIfTrue(pParse, pExpr->pRight, dest, jumpIfNull);
004249 sqlite3ExprCachePop(pParse);
004250 break;
004251 }
004252 case TK_NOT: {
004253 testcase( jumpIfNull==0 );
004254 sqlite3ExprIfFalse(pParse, pExpr->pLeft, dest, jumpIfNull);
004255 break;
004256 }
004257 case TK_IS:
004258 case TK_ISNOT:
004259 testcase( op==TK_IS );
004260 testcase( op==TK_ISNOT );
004261 op = (op==TK_IS) ? TK_EQ : TK_NE;
004262 jumpIfNull = SQLITE_NULLEQ;
004263 /* Fall thru */
004264 case TK_LT:
004265 case TK_LE:
004266 case TK_GT:
004267 case TK_GE:
004268 case TK_NE:
004269 case TK_EQ: {
004270 if( sqlite3ExprIsVector(pExpr->pLeft) ) goto default_expr;
004271 testcase( jumpIfNull==0 );
004272 r1 = sqlite3ExprCodeTemp(pParse, pExpr->pLeft, ®Free1);
004273 r2 = sqlite3ExprCodeTemp(pParse, pExpr->pRight, ®Free2);
004274 codeCompare(pParse, pExpr->pLeft, pExpr->pRight, op,
004275 r1, r2, dest, jumpIfNull);
004276 assert(TK_LT==OP_Lt); testcase(op==OP_Lt); VdbeCoverageIf(v,op==OP_Lt);
004277 assert(TK_LE==OP_Le); testcase(op==OP_Le); VdbeCoverageIf(v,op==OP_Le);
004278 assert(TK_GT==OP_Gt); testcase(op==OP_Gt); VdbeCoverageIf(v,op==OP_Gt);
004279 assert(TK_GE==OP_Ge); testcase(op==OP_Ge); VdbeCoverageIf(v,op==OP_Ge);
004280 assert(TK_EQ==OP_Eq); testcase(op==OP_Eq);
004281 VdbeCoverageIf(v, op==OP_Eq && jumpIfNull==SQLITE_NULLEQ);
004282 VdbeCoverageIf(v, op==OP_Eq && jumpIfNull!=SQLITE_NULLEQ);
004283 assert(TK_NE==OP_Ne); testcase(op==OP_Ne);
004284 VdbeCoverageIf(v, op==OP_Ne && jumpIfNull==SQLITE_NULLEQ);
004285 VdbeCoverageIf(v, op==OP_Ne && jumpIfNull!=SQLITE_NULLEQ);
004286 testcase( regFree1==0 );
004287 testcase( regFree2==0 );
004288 break;
004289 }
004290 case TK_ISNULL:
004291 case TK_NOTNULL: {
004292 assert( TK_ISNULL==OP_IsNull ); testcase( op==TK_ISNULL );
004293 assert( TK_NOTNULL==OP_NotNull ); testcase( op==TK_NOTNULL );
004294 r1 = sqlite3ExprCodeTemp(pParse, pExpr->pLeft, ®Free1);
004295 sqlite3VdbeAddOp2(v, op, r1, dest);
004296 VdbeCoverageIf(v, op==TK_ISNULL);
004297 VdbeCoverageIf(v, op==TK_NOTNULL);
004298 testcase( regFree1==0 );
004299 break;
004300 }
004301 case TK_BETWEEN: {
004302 testcase( jumpIfNull==0 );
004303 exprCodeBetween(pParse, pExpr, dest, sqlite3ExprIfTrue, jumpIfNull);
004304 break;
004305 }
004306 #ifndef SQLITE_OMIT_SUBQUERY
004307 case TK_IN: {
004308 int destIfFalse = sqlite3VdbeMakeLabel(v);
004309 int destIfNull = jumpIfNull ? dest : destIfFalse;
004310 sqlite3ExprCodeIN(pParse, pExpr, destIfFalse, destIfNull);
004311 sqlite3VdbeGoto(v, dest);
004312 sqlite3VdbeResolveLabel(v, destIfFalse);
004313 break;
004314 }
004315 #endif
004316 default: {
004317 default_expr:
004318 if( exprAlwaysTrue(pExpr) ){
004319 sqlite3VdbeGoto(v, dest);
004320 }else if( exprAlwaysFalse(pExpr) ){
004321 /* No-op */
004322 }else{
004323 r1 = sqlite3ExprCodeTemp(pParse, pExpr, ®Free1);
004324 sqlite3VdbeAddOp3(v, OP_If, r1, dest, jumpIfNull!=0);
004325 VdbeCoverage(v);
004326 testcase( regFree1==0 );
004327 testcase( jumpIfNull==0 );
004328 }
004329 break;
004330 }
004331 }
004332 sqlite3ReleaseTempReg(pParse, regFree1);
004333 sqlite3ReleaseTempReg(pParse, regFree2);
004334 }
004335
004336 /*
004337 ** Generate code for a boolean expression such that a jump is made
004338 ** to the label "dest" if the expression is false but execution
004339 ** continues straight thru if the expression is true.
004340 **
004341 ** If the expression evaluates to NULL (neither true nor false) then
004342 ** jump if jumpIfNull is SQLITE_JUMPIFNULL or fall through if jumpIfNull
004343 ** is 0.
004344 */
004345 void sqlite3ExprIfFalse(Parse *pParse, Expr *pExpr, int dest, int jumpIfNull){
004346 Vdbe *v = pParse->pVdbe;
004347 int op = 0;
004348 int regFree1 = 0;
004349 int regFree2 = 0;
004350 int r1, r2;
004351
004352 assert( jumpIfNull==SQLITE_JUMPIFNULL || jumpIfNull==0 );
004353 if( NEVER(v==0) ) return; /* Existence of VDBE checked by caller */
004354 if( pExpr==0 ) return;
004355
004356 /* The value of pExpr->op and op are related as follows:
004357 **
004358 ** pExpr->op op
004359 ** --------- ----------
004360 ** TK_ISNULL OP_NotNull
004361 ** TK_NOTNULL OP_IsNull
004362 ** TK_NE OP_Eq
004363 ** TK_EQ OP_Ne
004364 ** TK_GT OP_Le
004365 ** TK_LE OP_Gt
004366 ** TK_GE OP_Lt
004367 ** TK_LT OP_Ge
004368 **
004369 ** For other values of pExpr->op, op is undefined and unused.
004370 ** The value of TK_ and OP_ constants are arranged such that we
004371 ** can compute the mapping above using the following expression.
004372 ** Assert()s verify that the computation is correct.
004373 */
004374 op = ((pExpr->op+(TK_ISNULL&1))^1)-(TK_ISNULL&1);
004375
004376 /* Verify correct alignment of TK_ and OP_ constants
004377 */
004378 assert( pExpr->op!=TK_ISNULL || op==OP_NotNull );
004379 assert( pExpr->op!=TK_NOTNULL || op==OP_IsNull );
004380 assert( pExpr->op!=TK_NE || op==OP_Eq );
004381 assert( pExpr->op!=TK_EQ || op==OP_Ne );
004382 assert( pExpr->op!=TK_LT || op==OP_Ge );
004383 assert( pExpr->op!=TK_LE || op==OP_Gt );
004384 assert( pExpr->op!=TK_GT || op==OP_Le );
004385 assert( pExpr->op!=TK_GE || op==OP_Lt );
004386
004387 switch( pExpr->op ){
004388 case TK_AND: {
004389 testcase( jumpIfNull==0 );
004390 sqlite3ExprIfFalse(pParse, pExpr->pLeft, dest, jumpIfNull);
004391 sqlite3ExprCachePush(pParse);
004392 sqlite3ExprIfFalse(pParse, pExpr->pRight, dest, jumpIfNull);
004393 sqlite3ExprCachePop(pParse);
004394 break;
004395 }
004396 case TK_OR: {
004397 int d2 = sqlite3VdbeMakeLabel(v);
004398 testcase( jumpIfNull==0 );
004399 sqlite3ExprIfTrue(pParse, pExpr->pLeft, d2, jumpIfNull^SQLITE_JUMPIFNULL);
004400 sqlite3ExprCachePush(pParse);
004401 sqlite3ExprIfFalse(pParse, pExpr->pRight, dest, jumpIfNull);
004402 sqlite3VdbeResolveLabel(v, d2);
004403 sqlite3ExprCachePop(pParse);
004404 break;
004405 }
004406 case TK_NOT: {
004407 testcase( jumpIfNull==0 );
004408 sqlite3ExprIfTrue(pParse, pExpr->pLeft, dest, jumpIfNull);
004409 break;
004410 }
004411 case TK_IS:
004412 case TK_ISNOT:
004413 testcase( pExpr->op==TK_IS );
004414 testcase( pExpr->op==TK_ISNOT );
004415 op = (pExpr->op==TK_IS) ? TK_NE : TK_EQ;
004416 jumpIfNull = SQLITE_NULLEQ;
004417 /* Fall thru */
004418 case TK_LT:
004419 case TK_LE:
004420 case TK_GT:
004421 case TK_GE:
004422 case TK_NE:
004423 case TK_EQ: {
004424 if( sqlite3ExprIsVector(pExpr->pLeft) ) goto default_expr;
004425 testcase( jumpIfNull==0 );
004426 r1 = sqlite3ExprCodeTemp(pParse, pExpr->pLeft, ®Free1);
004427 r2 = sqlite3ExprCodeTemp(pParse, pExpr->pRight, ®Free2);
004428 codeCompare(pParse, pExpr->pLeft, pExpr->pRight, op,
004429 r1, r2, dest, jumpIfNull);
004430 assert(TK_LT==OP_Lt); testcase(op==OP_Lt); VdbeCoverageIf(v,op==OP_Lt);
004431 assert(TK_LE==OP_Le); testcase(op==OP_Le); VdbeCoverageIf(v,op==OP_Le);
004432 assert(TK_GT==OP_Gt); testcase(op==OP_Gt); VdbeCoverageIf(v,op==OP_Gt);
004433 assert(TK_GE==OP_Ge); testcase(op==OP_Ge); VdbeCoverageIf(v,op==OP_Ge);
004434 assert(TK_EQ==OP_Eq); testcase(op==OP_Eq);
004435 VdbeCoverageIf(v, op==OP_Eq && jumpIfNull!=SQLITE_NULLEQ);
004436 VdbeCoverageIf(v, op==OP_Eq && jumpIfNull==SQLITE_NULLEQ);
004437 assert(TK_NE==OP_Ne); testcase(op==OP_Ne);
004438 VdbeCoverageIf(v, op==OP_Ne && jumpIfNull!=SQLITE_NULLEQ);
004439 VdbeCoverageIf(v, op==OP_Ne && jumpIfNull==SQLITE_NULLEQ);
004440 testcase( regFree1==0 );
004441 testcase( regFree2==0 );
004442 break;
004443 }
004444 case TK_ISNULL:
004445 case TK_NOTNULL: {
004446 r1 = sqlite3ExprCodeTemp(pParse, pExpr->pLeft, ®Free1);
004447 sqlite3VdbeAddOp2(v, op, r1, dest);
004448 testcase( op==TK_ISNULL ); VdbeCoverageIf(v, op==TK_ISNULL);
004449 testcase( op==TK_NOTNULL ); VdbeCoverageIf(v, op==TK_NOTNULL);
004450 testcase( regFree1==0 );
004451 break;
004452 }
004453 case TK_BETWEEN: {
004454 testcase( jumpIfNull==0 );
004455 exprCodeBetween(pParse, pExpr, dest, sqlite3ExprIfFalse, jumpIfNull);
004456 break;
004457 }
004458 #ifndef SQLITE_OMIT_SUBQUERY
004459 case TK_IN: {
004460 if( jumpIfNull ){
004461 sqlite3ExprCodeIN(pParse, pExpr, dest, dest);
004462 }else{
004463 int destIfNull = sqlite3VdbeMakeLabel(v);
004464 sqlite3ExprCodeIN(pParse, pExpr, dest, destIfNull);
004465 sqlite3VdbeResolveLabel(v, destIfNull);
004466 }
004467 break;
004468 }
004469 #endif
004470 default: {
004471 default_expr:
004472 if( exprAlwaysFalse(pExpr) ){
004473 sqlite3VdbeGoto(v, dest);
004474 }else if( exprAlwaysTrue(pExpr) ){
004475 /* no-op */
004476 }else{
004477 r1 = sqlite3ExprCodeTemp(pParse, pExpr, ®Free1);
004478 sqlite3VdbeAddOp3(v, OP_IfNot, r1, dest, jumpIfNull!=0);
004479 VdbeCoverage(v);
004480 testcase( regFree1==0 );
004481 testcase( jumpIfNull==0 );
004482 }
004483 break;
004484 }
004485 }
004486 sqlite3ReleaseTempReg(pParse, regFree1);
004487 sqlite3ReleaseTempReg(pParse, regFree2);
004488 }
004489
004490 /*
004491 ** Like sqlite3ExprIfFalse() except that a copy is made of pExpr before
004492 ** code generation, and that copy is deleted after code generation. This
004493 ** ensures that the original pExpr is unchanged.
004494 */
004495 void sqlite3ExprIfFalseDup(Parse *pParse, Expr *pExpr, int dest,int jumpIfNull){
004496 sqlite3 *db = pParse->db;
004497 Expr *pCopy = sqlite3ExprDup(db, pExpr, 0);
004498 if( db->mallocFailed==0 ){
004499 sqlite3ExprIfFalse(pParse, pCopy, dest, jumpIfNull);
004500 }
004501 sqlite3ExprDelete(db, pCopy);
004502 }
004503
004504
004505 /*
004506 ** Do a deep comparison of two expression trees. Return 0 if the two
004507 ** expressions are completely identical. Return 1 if they differ only
004508 ** by a COLLATE operator at the top level. Return 2 if there are differences
004509 ** other than the top-level COLLATE operator.
004510 **
004511 ** If any subelement of pB has Expr.iTable==(-1) then it is allowed
004512 ** to compare equal to an equivalent element in pA with Expr.iTable==iTab.
004513 **
004514 ** The pA side might be using TK_REGISTER. If that is the case and pB is
004515 ** not using TK_REGISTER but is otherwise equivalent, then still return 0.
004516 **
004517 ** Sometimes this routine will return 2 even if the two expressions
004518 ** really are equivalent. If we cannot prove that the expressions are
004519 ** identical, we return 2 just to be safe. So if this routine
004520 ** returns 2, then you do not really know for certain if the two
004521 ** expressions are the same. But if you get a 0 or 1 return, then you
004522 ** can be sure the expressions are the same. In the places where
004523 ** this routine is used, it does not hurt to get an extra 2 - that
004524 ** just might result in some slightly slower code. But returning
004525 ** an incorrect 0 or 1 could lead to a malfunction.
004526 */
004527 int sqlite3ExprCompare(Expr *pA, Expr *pB, int iTab){
004528 u32 combinedFlags;
004529 if( pA==0 || pB==0 ){
004530 return pB==pA ? 0 : 2;
004531 }
004532 combinedFlags = pA->flags | pB->flags;
004533 if( combinedFlags & EP_IntValue ){
004534 if( (pA->flags&pB->flags&EP_IntValue)!=0 && pA->u.iValue==pB->u.iValue ){
004535 return 0;
004536 }
004537 return 2;
004538 }
004539 if( pA->op!=pB->op ){
004540 if( pA->op==TK_COLLATE && sqlite3ExprCompare(pA->pLeft, pB, iTab)<2 ){
004541 return 1;
004542 }
004543 if( pB->op==TK_COLLATE && sqlite3ExprCompare(pA, pB->pLeft, iTab)<2 ){
004544 return 1;
004545 }
004546 return 2;
004547 }
004548 if( pA->op!=TK_COLUMN && pA->op!=TK_AGG_COLUMN && pA->u.zToken ){
004549 if( pA->op==TK_FUNCTION ){
004550 if( sqlite3StrICmp(pA->u.zToken,pB->u.zToken)!=0 ) return 2;
004551 }else if( strcmp(pA->u.zToken,pB->u.zToken)!=0 ){
004552 return pA->op==TK_COLLATE ? 1 : 2;
004553 }
004554 }
004555 if( (pA->flags & EP_Distinct)!=(pB->flags & EP_Distinct) ) return 2;
004556 if( ALWAYS((combinedFlags & EP_TokenOnly)==0) ){
004557 if( combinedFlags & EP_xIsSelect ) return 2;
004558 if( sqlite3ExprCompare(pA->pLeft, pB->pLeft, iTab) ) return 2;
004559 if( sqlite3ExprCompare(pA->pRight, pB->pRight, iTab) ) return 2;
004560 if( sqlite3ExprListCompare(pA->x.pList, pB->x.pList, iTab) ) return 2;
004561 if( ALWAYS((combinedFlags & EP_Reduced)==0) && pA->op!=TK_STRING ){
004562 if( pA->iColumn!=pB->iColumn ) return 2;
004563 if( pA->iTable!=pB->iTable
004564 && (pA->iTable!=iTab || NEVER(pB->iTable>=0)) ) return 2;
004565 }
004566 }
004567 return 0;
004568 }
004569
004570 /*
004571 ** Compare two ExprList objects. Return 0 if they are identical and
004572 ** non-zero if they differ in any way.
004573 **
004574 ** If any subelement of pB has Expr.iTable==(-1) then it is allowed
004575 ** to compare equal to an equivalent element in pA with Expr.iTable==iTab.
004576 **
004577 ** This routine might return non-zero for equivalent ExprLists. The
004578 ** only consequence will be disabled optimizations. But this routine
004579 ** must never return 0 if the two ExprList objects are different, or
004580 ** a malfunction will result.
004581 **
004582 ** Two NULL pointers are considered to be the same. But a NULL pointer
004583 ** always differs from a non-NULL pointer.
004584 */
004585 int sqlite3ExprListCompare(ExprList *pA, ExprList *pB, int iTab){
004586 int i;
004587 if( pA==0 && pB==0 ) return 0;
004588 if( pA==0 || pB==0 ) return 1;
004589 if( pA->nExpr!=pB->nExpr ) return 1;
004590 for(i=0; i<pA->nExpr; i++){
004591 Expr *pExprA = pA->a[i].pExpr;
004592 Expr *pExprB = pB->a[i].pExpr;
004593 if( pA->a[i].sortOrder!=pB->a[i].sortOrder ) return 1;
004594 if( sqlite3ExprCompare(pExprA, pExprB, iTab) ) return 1;
004595 }
004596 return 0;
004597 }
004598
004599 /*
004600 ** Return true if we can prove the pE2 will always be true if pE1 is
004601 ** true. Return false if we cannot complete the proof or if pE2 might
004602 ** be false. Examples:
004603 **
004604 ** pE1: x==5 pE2: x==5 Result: true
004605 ** pE1: x>0 pE2: x==5 Result: false
004606 ** pE1: x=21 pE2: x=21 OR y=43 Result: true
004607 ** pE1: x!=123 pE2: x IS NOT NULL Result: true
004608 ** pE1: x!=?1 pE2: x IS NOT NULL Result: true
004609 ** pE1: x IS NULL pE2: x IS NOT NULL Result: false
004610 ** pE1: x IS ?2 pE2: x IS NOT NULL Reuslt: false
004611 **
004612 ** When comparing TK_COLUMN nodes between pE1 and pE2, if pE2 has
004613 ** Expr.iTable<0 then assume a table number given by iTab.
004614 **
004615 ** When in doubt, return false. Returning true might give a performance
004616 ** improvement. Returning false might cause a performance reduction, but
004617 ** it will always give the correct answer and is hence always safe.
004618 */
004619 int sqlite3ExprImpliesExpr(Expr *pE1, Expr *pE2, int iTab){
004620 if( sqlite3ExprCompare(pE1, pE2, iTab)==0 ){
004621 return 1;
004622 }
004623 if( pE2->op==TK_OR
004624 && (sqlite3ExprImpliesExpr(pE1, pE2->pLeft, iTab)
004625 || sqlite3ExprImpliesExpr(pE1, pE2->pRight, iTab) )
004626 ){
004627 return 1;
004628 }
004629 if( pE2->op==TK_NOTNULL && pE1->op!=TK_ISNULL && pE1->op!=TK_IS ){
004630 Expr *pX = sqlite3ExprSkipCollate(pE1->pLeft);
004631 testcase( pX!=pE1->pLeft );
004632 if( sqlite3ExprCompare(pX, pE2->pLeft, iTab)==0 ) return 1;
004633 }
004634 return 0;
004635 }
004636
004637 /*
004638 ** An instance of the following structure is used by the tree walker
004639 ** to determine if an expression can be evaluated by reference to the
004640 ** index only, without having to do a search for the corresponding
004641 ** table entry. The IdxCover.pIdx field is the index. IdxCover.iCur
004642 ** is the cursor for the table.
004643 */
004644 struct IdxCover {
004645 Index *pIdx; /* The index to be tested for coverage */
004646 int iCur; /* Cursor number for the table corresponding to the index */
004647 };
004648
004649 /*
004650 ** Check to see if there are references to columns in table
004651 ** pWalker->u.pIdxCover->iCur can be satisfied using the index
004652 ** pWalker->u.pIdxCover->pIdx.
004653 */
004654 static int exprIdxCover(Walker *pWalker, Expr *pExpr){
004655 if( pExpr->op==TK_COLUMN
004656 && pExpr->iTable==pWalker->u.pIdxCover->iCur
004657 && sqlite3ColumnOfIndex(pWalker->u.pIdxCover->pIdx, pExpr->iColumn)<0
004658 ){
004659 pWalker->eCode = 1;
004660 return WRC_Abort;
004661 }
004662 return WRC_Continue;
004663 }
004664
004665 /*
004666 ** Determine if an index pIdx on table with cursor iCur contains will
004667 ** the expression pExpr. Return true if the index does cover the
004668 ** expression and false if the pExpr expression references table columns
004669 ** that are not found in the index pIdx.
004670 **
004671 ** An index covering an expression means that the expression can be
004672 ** evaluated using only the index and without having to lookup the
004673 ** corresponding table entry.
004674 */
004675 int sqlite3ExprCoveredByIndex(
004676 Expr *pExpr, /* The index to be tested */
004677 int iCur, /* The cursor number for the corresponding table */
004678 Index *pIdx /* The index that might be used for coverage */
004679 ){
004680 Walker w;
004681 struct IdxCover xcov;
004682 memset(&w, 0, sizeof(w));
004683 xcov.iCur = iCur;
004684 xcov.pIdx = pIdx;
004685 w.xExprCallback = exprIdxCover;
004686 w.u.pIdxCover = &xcov;
004687 sqlite3WalkExpr(&w, pExpr);
004688 return !w.eCode;
004689 }
004690
004691
004692 /*
004693 ** An instance of the following structure is used by the tree walker
004694 ** to count references to table columns in the arguments of an
004695 ** aggregate function, in order to implement the
004696 ** sqlite3FunctionThisSrc() routine.
004697 */
004698 struct SrcCount {
004699 SrcList *pSrc; /* One particular FROM clause in a nested query */
004700 int nThis; /* Number of references to columns in pSrcList */
004701 int nOther; /* Number of references to columns in other FROM clauses */
004702 };
004703
004704 /*
004705 ** Count the number of references to columns.
004706 */
004707 static int exprSrcCount(Walker *pWalker, Expr *pExpr){
004708 /* The NEVER() on the second term is because sqlite3FunctionUsesThisSrc()
004709 ** is always called before sqlite3ExprAnalyzeAggregates() and so the
004710 ** TK_COLUMNs have not yet been converted into TK_AGG_COLUMN. If
004711 ** sqlite3FunctionUsesThisSrc() is used differently in the future, the
004712 ** NEVER() will need to be removed. */
004713 if( pExpr->op==TK_COLUMN || NEVER(pExpr->op==TK_AGG_COLUMN) ){
004714 int i;
004715 struct SrcCount *p = pWalker->u.pSrcCount;
004716 SrcList *pSrc = p->pSrc;
004717 int nSrc = pSrc ? pSrc->nSrc : 0;
004718 for(i=0; i<nSrc; i++){
004719 if( pExpr->iTable==pSrc->a[i].iCursor ) break;
004720 }
004721 if( i<nSrc ){
004722 p->nThis++;
004723 }else{
004724 p->nOther++;
004725 }
004726 }
004727 return WRC_Continue;
004728 }
004729
004730 /*
004731 ** Determine if any of the arguments to the pExpr Function reference
004732 ** pSrcList. Return true if they do. Also return true if the function
004733 ** has no arguments or has only constant arguments. Return false if pExpr
004734 ** references columns but not columns of tables found in pSrcList.
004735 */
004736 int sqlite3FunctionUsesThisSrc(Expr *pExpr, SrcList *pSrcList){
004737 Walker w;
004738 struct SrcCount cnt;
004739 assert( pExpr->op==TK_AGG_FUNCTION );
004740 memset(&w, 0, sizeof(w));
004741 w.xExprCallback = exprSrcCount;
004742 w.u.pSrcCount = &cnt;
004743 cnt.pSrc = pSrcList;
004744 cnt.nThis = 0;
004745 cnt.nOther = 0;
004746 sqlite3WalkExprList(&w, pExpr->x.pList);
004747 return cnt.nThis>0 || cnt.nOther==0;
004748 }
004749
004750 /*
004751 ** Add a new element to the pAggInfo->aCol[] array. Return the index of
004752 ** the new element. Return a negative number if malloc fails.
004753 */
004754 static int addAggInfoColumn(sqlite3 *db, AggInfo *pInfo){
004755 int i;
004756 pInfo->aCol = sqlite3ArrayAllocate(
004757 db,
004758 pInfo->aCol,
004759 sizeof(pInfo->aCol[0]),
004760 &pInfo->nColumn,
004761 &i
004762 );
004763 return i;
004764 }
004765
004766 /*
004767 ** Add a new element to the pAggInfo->aFunc[] array. Return the index of
004768 ** the new element. Return a negative number if malloc fails.
004769 */
004770 static int addAggInfoFunc(sqlite3 *db, AggInfo *pInfo){
004771 int i;
004772 pInfo->aFunc = sqlite3ArrayAllocate(
004773 db,
004774 pInfo->aFunc,
004775 sizeof(pInfo->aFunc[0]),
004776 &pInfo->nFunc,
004777 &i
004778 );
004779 return i;
004780 }
004781
004782 /*
004783 ** This is the xExprCallback for a tree walker. It is used to
004784 ** implement sqlite3ExprAnalyzeAggregates(). See sqlite3ExprAnalyzeAggregates
004785 ** for additional information.
004786 */
004787 static int analyzeAggregate(Walker *pWalker, Expr *pExpr){
004788 int i;
004789 NameContext *pNC = pWalker->u.pNC;
004790 Parse *pParse = pNC->pParse;
004791 SrcList *pSrcList = pNC->pSrcList;
004792 AggInfo *pAggInfo = pNC->pAggInfo;
004793
004794 switch( pExpr->op ){
004795 case TK_AGG_COLUMN:
004796 case TK_COLUMN: {
004797 testcase( pExpr->op==TK_AGG_COLUMN );
004798 testcase( pExpr->op==TK_COLUMN );
004799 /* Check to see if the column is in one of the tables in the FROM
004800 ** clause of the aggregate query */
004801 if( ALWAYS(pSrcList!=0) ){
004802 struct SrcList_item *pItem = pSrcList->a;
004803 for(i=0; i<pSrcList->nSrc; i++, pItem++){
004804 struct AggInfo_col *pCol;
004805 assert( !ExprHasProperty(pExpr, EP_TokenOnly|EP_Reduced) );
004806 if( pExpr->iTable==pItem->iCursor ){
004807 /* If we reach this point, it means that pExpr refers to a table
004808 ** that is in the FROM clause of the aggregate query.
004809 **
004810 ** Make an entry for the column in pAggInfo->aCol[] if there
004811 ** is not an entry there already.
004812 */
004813 int k;
004814 pCol = pAggInfo->aCol;
004815 for(k=0; k<pAggInfo->nColumn; k++, pCol++){
004816 if( pCol->iTable==pExpr->iTable &&
004817 pCol->iColumn==pExpr->iColumn ){
004818 break;
004819 }
004820 }
004821 if( (k>=pAggInfo->nColumn)
004822 && (k = addAggInfoColumn(pParse->db, pAggInfo))>=0
004823 ){
004824 pCol = &pAggInfo->aCol[k];
004825 pCol->pTab = pExpr->pTab;
004826 pCol->iTable = pExpr->iTable;
004827 pCol->iColumn = pExpr->iColumn;
004828 pCol->iMem = ++pParse->nMem;
004829 pCol->iSorterColumn = -1;
004830 pCol->pExpr = pExpr;
004831 if( pAggInfo->pGroupBy ){
004832 int j, n;
004833 ExprList *pGB = pAggInfo->pGroupBy;
004834 struct ExprList_item *pTerm = pGB->a;
004835 n = pGB->nExpr;
004836 for(j=0; j<n; j++, pTerm++){
004837 Expr *pE = pTerm->pExpr;
004838 if( pE->op==TK_COLUMN && pE->iTable==pExpr->iTable &&
004839 pE->iColumn==pExpr->iColumn ){
004840 pCol->iSorterColumn = j;
004841 break;
004842 }
004843 }
004844 }
004845 if( pCol->iSorterColumn<0 ){
004846 pCol->iSorterColumn = pAggInfo->nSortingColumn++;
004847 }
004848 }
004849 /* There is now an entry for pExpr in pAggInfo->aCol[] (either
004850 ** because it was there before or because we just created it).
004851 ** Convert the pExpr to be a TK_AGG_COLUMN referring to that
004852 ** pAggInfo->aCol[] entry.
004853 */
004854 ExprSetVVAProperty(pExpr, EP_NoReduce);
004855 pExpr->pAggInfo = pAggInfo;
004856 pExpr->op = TK_AGG_COLUMN;
004857 pExpr->iAgg = (i16)k;
004858 break;
004859 } /* endif pExpr->iTable==pItem->iCursor */
004860 } /* end loop over pSrcList */
004861 }
004862 return WRC_Prune;
004863 }
004864 case TK_AGG_FUNCTION: {
004865 if( (pNC->ncFlags & NC_InAggFunc)==0
004866 && pWalker->walkerDepth==pExpr->op2
004867 ){
004868 /* Check to see if pExpr is a duplicate of another aggregate
004869 ** function that is already in the pAggInfo structure
004870 */
004871 struct AggInfo_func *pItem = pAggInfo->aFunc;
004872 for(i=0; i<pAggInfo->nFunc; i++, pItem++){
004873 if( sqlite3ExprCompare(pItem->pExpr, pExpr, -1)==0 ){
004874 break;
004875 }
004876 }
004877 if( i>=pAggInfo->nFunc ){
004878 /* pExpr is original. Make a new entry in pAggInfo->aFunc[]
004879 */
004880 u8 enc = ENC(pParse->db);
004881 i = addAggInfoFunc(pParse->db, pAggInfo);
004882 if( i>=0 ){
004883 assert( !ExprHasProperty(pExpr, EP_xIsSelect) );
004884 pItem = &pAggInfo->aFunc[i];
004885 pItem->pExpr = pExpr;
004886 pItem->iMem = ++pParse->nMem;
004887 assert( !ExprHasProperty(pExpr, EP_IntValue) );
004888 pItem->pFunc = sqlite3FindFunction(pParse->db,
004889 pExpr->u.zToken,
004890 pExpr->x.pList ? pExpr->x.pList->nExpr : 0, enc, 0);
004891 if( pExpr->flags & EP_Distinct ){
004892 pItem->iDistinct = pParse->nTab++;
004893 }else{
004894 pItem->iDistinct = -1;
004895 }
004896 }
004897 }
004898 /* Make pExpr point to the appropriate pAggInfo->aFunc[] entry
004899 */
004900 assert( !ExprHasProperty(pExpr, EP_TokenOnly|EP_Reduced) );
004901 ExprSetVVAProperty(pExpr, EP_NoReduce);
004902 pExpr->iAgg = (i16)i;
004903 pExpr->pAggInfo = pAggInfo;
004904 return WRC_Prune;
004905 }else{
004906 return WRC_Continue;
004907 }
004908 }
004909 }
004910 return WRC_Continue;
004911 }
004912 static int analyzeAggregatesInSelect(Walker *pWalker, Select *pSelect){
004913 UNUSED_PARAMETER(pWalker);
004914 UNUSED_PARAMETER(pSelect);
004915 return WRC_Continue;
004916 }
004917
004918 /*
004919 ** Analyze the pExpr expression looking for aggregate functions and
004920 ** for variables that need to be added to AggInfo object that pNC->pAggInfo
004921 ** points to. Additional entries are made on the AggInfo object as
004922 ** necessary.
004923 **
004924 ** This routine should only be called after the expression has been
004925 ** analyzed by sqlite3ResolveExprNames().
004926 */
004927 void sqlite3ExprAnalyzeAggregates(NameContext *pNC, Expr *pExpr){
004928 Walker w;
004929 memset(&w, 0, sizeof(w));
004930 w.xExprCallback = analyzeAggregate;
004931 w.xSelectCallback = analyzeAggregatesInSelect;
004932 w.u.pNC = pNC;
004933 assert( pNC->pSrcList!=0 );
004934 sqlite3WalkExpr(&w, pExpr);
004935 }
004936
004937 /*
004938 ** Call sqlite3ExprAnalyzeAggregates() for every expression in an
004939 ** expression list. Return the number of errors.
004940 **
004941 ** If an error is found, the analysis is cut short.
004942 */
004943 void sqlite3ExprAnalyzeAggList(NameContext *pNC, ExprList *pList){
004944 struct ExprList_item *pItem;
004945 int i;
004946 if( pList ){
004947 for(pItem=pList->a, i=0; i<pList->nExpr; i++, pItem++){
004948 sqlite3ExprAnalyzeAggregates(pNC, pItem->pExpr);
004949 }
004950 }
004951 }
004952
004953 /*
004954 ** Allocate a single new register for use to hold some intermediate result.
004955 */
004956 int sqlite3GetTempReg(Parse *pParse){
004957 if( pParse->nTempReg==0 ){
004958 return ++pParse->nMem;
004959 }
004960 return pParse->aTempReg[--pParse->nTempReg];
004961 }
004962
004963 /*
004964 ** Deallocate a register, making available for reuse for some other
004965 ** purpose.
004966 **
004967 ** If a register is currently being used by the column cache, then
004968 ** the deallocation is deferred until the column cache line that uses
004969 ** the register becomes stale.
004970 */
004971 void sqlite3ReleaseTempReg(Parse *pParse, int iReg){
004972 if( iReg && pParse->nTempReg<ArraySize(pParse->aTempReg) ){
004973 int i;
004974 struct yColCache *p;
004975 for(i=0, p=pParse->aColCache; i<pParse->nColCache; i++, p++){
004976 if( p->iReg==iReg ){
004977 p->tempReg = 1;
004978 return;
004979 }
004980 }
004981 pParse->aTempReg[pParse->nTempReg++] = iReg;
004982 }
004983 }
004984
004985 /*
004986 ** Allocate or deallocate a block of nReg consecutive registers.
004987 */
004988 int sqlite3GetTempRange(Parse *pParse, int nReg){
004989 int i, n;
004990 if( nReg==1 ) return sqlite3GetTempReg(pParse);
004991 i = pParse->iRangeReg;
004992 n = pParse->nRangeReg;
004993 if( nReg<=n ){
004994 assert( !usedAsColumnCache(pParse, i, i+n-1) );
004995 pParse->iRangeReg += nReg;
004996 pParse->nRangeReg -= nReg;
004997 }else{
004998 i = pParse->nMem+1;
004999 pParse->nMem += nReg;
005000 }
005001 return i;
005002 }
005003 void sqlite3ReleaseTempRange(Parse *pParse, int iReg, int nReg){
005004 if( nReg==1 ){
005005 sqlite3ReleaseTempReg(pParse, iReg);
005006 return;
005007 }
005008 sqlite3ExprCacheRemove(pParse, iReg, nReg);
005009 if( nReg>pParse->nRangeReg ){
005010 pParse->nRangeReg = nReg;
005011 pParse->iRangeReg = iReg;
005012 }
005013 }
005014
005015 /*
005016 ** Mark all temporary registers as being unavailable for reuse.
005017 */
005018 void sqlite3ClearTempRegCache(Parse *pParse){
005019 pParse->nTempReg = 0;
005020 pParse->nRangeReg = 0;
005021 }
005022
005023 /*
005024 ** Validate that no temporary register falls within the range of
005025 ** iFirst..iLast, inclusive. This routine is only call from within assert()
005026 ** statements.
005027 */
005028 #ifdef SQLITE_DEBUG
005029 int sqlite3NoTempsInRange(Parse *pParse, int iFirst, int iLast){
005030 int i;
005031 if( pParse->nRangeReg>0
005032 && pParse->iRangeReg+pParse->nRangeReg<iLast
005033 && pParse->iRangeReg>=iFirst
005034 ){
005035 return 0;
005036 }
005037 for(i=0; i<pParse->nTempReg; i++){
005038 if( pParse->aTempReg[i]>=iFirst && pParse->aTempReg[i]<=iLast ){
005039 return 0;
005040 }
005041 }
005042 return 1;
005043 }
005044 #endif /* SQLITE_DEBUG */