/*

** 2001 September 15

**

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

** a legal notice, here is a blessing:

**

** May you do good and not evil.

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

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

**

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

** This file contains routines used for analyzing expressions and

** for generating VDBE code that evaluates expressions in SQLite.

*/

#include "sqliteInt.h"

/* Forward declarations */

static void exprCodeBetween(Parse*,Expr*,int,void(*)(Parse*,Expr*,int,int),int);

static int exprCodeVector(Parse *pParse, Expr *p, int *piToFree);

/*

** Return the affinity character for a single column of a table.

*/

char sqlite3TableColumnAffinity(Table *pTab, int iCol){

assert( iCol<pTab->nCol );

return iCol>=0 ? pTab->aCol[iCol].affinity : SQLITE_AFF_INTEGER;

}

/*

** Return the 'affinity' of the expression pExpr if any.

**

** If pExpr is a column, a reference to a column via an 'AS' alias,

** or a sub-select with a column as the return value, then the

** affinity of that column is returned. Otherwise, 0x00 is returned,

** indicating no affinity for the expression.

**

** i.e. the WHERE clause expressions in the following statements all

** have an affinity:

**

** CREATE TABLE t1(a);

** SELECT * FROM t1 WHERE a;

** SELECT a AS b FROM t1 WHERE b;

** SELECT * FROM t1 WHERE (select a from t1);

*/

char sqlite3ExprAffinity(Expr *pExpr){

int op;

pExpr = sqlite3ExprSkipCollate(pExpr);

if( pExpr->flags & EP_Generic ) return 0;

op = pExpr->op;

if( op==TK_SELECT ){

assert( pExpr->flags&EP_xIsSelect );

return sqlite3ExprAffinity(pExpr->x.pSelect->pEList->a[0].pExpr);

}

if( op==TK_REGISTER ) op = pExpr->op2;

#ifndef SQLITE_OMIT_CAST

if( op==TK_CAST ){

assert( !ExprHasProperty(pExpr, EP_IntValue) );

return sqlite3AffinityType(pExpr->u.zToken, 0);

}

#endif

if( (op==TK_AGG_COLUMN || op==TK_COLUMN) && pExpr->y.pTab ){

return sqlite3TableColumnAffinity(pExpr->y.pTab, pExpr->iColumn);

}

if( op==TK_SELECT_COLUMN ){

assert( pExpr->pLeft->flags&EP_xIsSelect );

return sqlite3ExprAffinity(

pExpr->pLeft->x.pSelect->pEList->a[pExpr->iColumn].pExpr

);

}

return pExpr->affinity;

}

/*

** Set the collating sequence for expression pExpr to be the collating

** sequence named by pToken. Return a pointer to a new Expr node that

** implements the COLLATE operator.

**

** If a memory allocation error occurs, that fact is recorded in pParse->db

** and the pExpr parameter is returned unchanged.

*/

Expr *sqlite3ExprAddCollateToken(

Parse *pParse, /* Parsing context */

Expr *pExpr, /* Add the "COLLATE" clause to this expression */

const Token *pCollName, /* Name of collating sequence */

int dequote /* True to dequote pCollName */

){

if( pCollName->n>0 ){

Expr *pNew = sqlite3ExprAlloc(pParse->db, TK_COLLATE, pCollName, dequote);

if( pNew ){

pNew->pLeft = pExpr;

pNew->flags |= EP_Collate|EP_Skip;

pExpr = pNew;

}

}

return pExpr;

}

Expr *sqlite3ExprAddCollateString(Parse *pParse, Expr *pExpr, const char *zC){

Token s;

assert( zC!=0 );

sqlite3TokenInit(&s, (char*)zC);

return sqlite3ExprAddCollateToken(pParse, pExpr, &s, 0);

}

/*

** Skip over any TK_COLLATE operators and any unlikely()

** or likelihood() function at the root of an expression.

*/

Expr *sqlite3ExprSkipCollate(Expr *pExpr){

while( pExpr && ExprHasProperty(pExpr, EP_Skip) ){

if( ExprHasProperty(pExpr, EP_Unlikely) ){

assert( !ExprHasProperty(pExpr, EP_xIsSelect) );

assert( pExpr->x.pList->nExpr>0 );

assert( pExpr->op==TK_FUNCTION );

pExpr = pExpr->x.pList->a[0].pExpr;

}else{

assert( pExpr->op==TK_COLLATE );

pExpr = pExpr->pLeft;

}

}

return pExpr;

}

/*

** Return the collation sequence for the expression pExpr. If

** there is no defined collating sequence, return NULL.

**

** See also: sqlite3ExprNNCollSeq()

**

** The sqlite3ExprNNCollSeq() works the same exact that it returns the

** default collation if pExpr has no defined collation.

**

** The collating sequence might be determined by a COLLATE operator

** or by the presence of a column with a defined collating sequence.

** COLLATE operators take first precedence. Left operands take

** precedence over right operands.

*/

CollSeq *sqlite3ExprCollSeq(Parse *pParse, Expr *pExpr){

sqlite3 *db = pParse->db;

CollSeq *pColl = 0;

Expr *p = pExpr;

while( p ){

int op = p->op;

if( p->flags & EP_Generic ) break;

if( (op==TK_AGG_COLUMN || op==TK_COLUMN

|| op==TK_REGISTER || op==TK_TRIGGER)

&& p->y.pTab!=0

){

/* op==TK_REGISTER && p->y.pTab!=0 happens when pExpr was originally

** a TK_COLUMN but was previously evaluated and cached in a register */

int j = p->iColumn;

if( j>=0 ){

const char *zColl = p->y.pTab->aCol[j].zColl;

pColl = sqlite3FindCollSeq(db, ENC(db), zColl, 0);

}

break;

}

if( op==TK_CAST || op==TK_UPLUS ){

p = p->pLeft;

continue;

}

if( op==TK_COLLATE || (op==TK_REGISTER && p->op2==TK_COLLATE) ){

pColl = sqlite3GetCollSeq(pParse, ENC(db), 0, p->u.zToken);

break;

}

if( p->flags & EP_Collate ){

if( p->pLeft && (p->pLeft->flags & EP_Collate)!=0 ){

p = p->pLeft;

}else{

Expr *pNext = p->pRight;

/* The Expr.x union is never used at the same time as Expr.pRight */

assert( p->x.pList==0 || p->pRight==0 );

/* p->flags holds EP_Collate and p->pLeft->flags does not. And

** p->x.pSelect cannot. So if p->x.pLeft exists, it must hold at

** least one EP_Collate. Thus the following two ALWAYS. */

if( p->x.pList!=0 && ALWAYS(!ExprHasProperty(p, EP_xIsSelect)) ){

int i;

for(i=0; ALWAYS(i<p->x.pList->nExpr); i++){

if( ExprHasProperty(p->x.pList->a[i].pExpr, EP_Collate) ){

pNext = p->x.pList->a[i].pExpr;

break;

}

}

}

p = pNext;

}

}else{

break;

}

}

if( sqlite3CheckCollSeq(pParse, pColl) ){

pColl = 0;

}

return pColl;

}

/*

** Return the collation sequence for the expression pExpr. If

** there is no defined collating sequence, return a pointer to the

** defautl collation sequence.

**

** See also: sqlite3ExprCollSeq()

**

** The sqlite3ExprCollSeq() routine works the same except that it

** returns NULL if there is no defined collation.

*/

CollSeq *sqlite3ExprNNCollSeq(Parse *pParse, Expr *pExpr){

CollSeq *p = sqlite3ExprCollSeq(pParse, pExpr);

if( p==0 ) p = pParse->db->pDfltColl;

assert( p!=0 );

return p;

}

/*

** Return TRUE if the two expressions have equivalent collating sequences.

*/

int sqlite3ExprCollSeqMatch(Parse *pParse, Expr *pE1, Expr *pE2){

CollSeq *pColl1 = sqlite3ExprNNCollSeq(pParse, pE1);

CollSeq *pColl2 = sqlite3ExprNNCollSeq(pParse, pE2);

return sqlite3StrICmp(pColl1->zName, pColl2->zName)==0;

}

/*

** pExpr is an operand of a comparison operator. aff2 is the

** type affinity of the other operand. This routine returns the

** type affinity that should be used for the comparison operator.

*/

char sqlite3CompareAffinity(Expr *pExpr, char aff2){

char aff1 = sqlite3ExprAffinity(pExpr);

if( aff1 && aff2 ){

/* Both sides of the comparison are columns. If one has numeric

** affinity, use that. Otherwise use no affinity.

*/

if( sqlite3IsNumericAffinity(aff1) || sqlite3IsNumericAffinity(aff2) ){

return SQLITE_AFF_NUMERIC;

}else{

return SQLITE_AFF_BLOB;

}

}else if( !aff1 && !aff2 ){

/* Neither side of the comparison is a column. Compare the

** results directly.

*/

return SQLITE_AFF_BLOB;

}else{

/* One side is a column, the other is not. Use the columns affinity. */

assert( aff1==0 || aff2==0 );

return (aff1 + aff2);

}

}

/*

** pExpr is a comparison operator. Return the type affinity that should

** be applied to both operands prior to doing the comparison.

*/

static char comparisonAffinity(Expr *pExpr){

char aff;

assert( pExpr->op==TK_EQ || pExpr->op==TK_IN || pExpr->op==TK_LT ||

pExpr->op==TK_GT || pExpr->op==TK_GE || pExpr->op==TK_LE ||

pExpr->op==TK_NE || pExpr->op==TK_IS || pExpr->op==TK_ISNOT );

assert( pExpr->pLeft );

aff = sqlite3ExprAffinity(pExpr->pLeft);

if( pExpr->pRight ){

aff = sqlite3CompareAffinity(pExpr->pRight, aff);

}else if( ExprHasProperty(pExpr, EP_xIsSelect) ){

aff = sqlite3CompareAffinity(pExpr->x.pSelect->pEList->a[0].pExpr, aff);

}else if( aff==0 ){

aff = SQLITE_AFF_BLOB;

}

return aff;

}

/*

** pExpr is a comparison expression, eg. '=', '<', IN(...) etc.

** idx_affinity is the affinity of an indexed column. Return true

** if the index with affinity idx_affinity may be used to implement

** the comparison in pExpr.

*/

int sqlite3IndexAffinityOk(Expr *pExpr, char idx_affinity){

char aff = comparisonAffinity(pExpr);

switch( aff ){

case SQLITE_AFF_BLOB:

return 1;

case SQLITE_AFF_TEXT:

return idx_affinity==SQLITE_AFF_TEXT;

default:

return sqlite3IsNumericAffinity(idx_affinity);

}

}

/*

** Return the P5 value that should be used for a binary comparison

** opcode (OP_Eq, OP_Ge etc.) used to compare pExpr1 and pExpr2.

*/

static u8 binaryCompareP5(Expr *pExpr1, Expr *pExpr2, int jumpIfNull){

u8 aff = (char)sqlite3ExprAffinity(pExpr2);

aff = (u8)sqlite3CompareAffinity(pExpr1, aff) | (u8)jumpIfNull;

return aff;

}

/*

** Return a pointer to the collation sequence that should be used by

** a binary comparison operator comparing pLeft and pRight.

**

** If the left hand expression has a collating sequence type, then it is

** used. Otherwise the collation sequence for the right hand expression

** is used, or the default (BINARY) if neither expression has a collating

** type.

**

** Argument pRight (but not pLeft) may be a null pointer. In this case,

** it is not considered.

*/

CollSeq *sqlite3BinaryCompareCollSeq(

Parse *pParse,

Expr *pLeft,

Expr *pRight

){

CollSeq *pColl;

assert( pLeft );

if( pLeft->flags & EP_Collate ){

pColl = sqlite3ExprCollSeq(pParse, pLeft);

}else if( pRight && (pRight->flags & EP_Collate)!=0 ){

pColl = sqlite3ExprCollSeq(pParse, pRight);

}else{

pColl = sqlite3ExprCollSeq(pParse, pLeft);

if( !pColl ){

pColl = sqlite3ExprCollSeq(pParse, pRight);

}

}

return pColl;

}

/*

** Generate code for a comparison operator.

*/

static int codeCompare(

Parse *pParse, /* The parsing (and code generating) context */

Expr *pLeft, /* The left operand */

Expr *pRight, /* The right operand */

int opcode, /* The comparison opcode */

int in1, int in2, /* Register holding operands */

int dest, /* Jump here if true. */

int jumpIfNull /* If true, jump if either operand is NULL */

){

int p5;

int addr;

CollSeq *p4;

p4 = sqlite3BinaryCompareCollSeq(pParse, pLeft, pRight);

p5 = binaryCompareP5(pLeft, pRight, jumpIfNull);

addr = sqlite3VdbeAddOp4(pParse->pVdbe, opcode, in2, dest, in1,

(void*)p4, P4_COLLSEQ);

sqlite3VdbeChangeP5(pParse->pVdbe, (u8)p5);

return addr;

}

/*

** Return true if expression pExpr is a vector, or false otherwise.

**

** A vector is defined as any expression that results in two or more

** columns of result. Every TK_VECTOR node is an vector because the

** parser will not generate a TK_VECTOR with fewer than two entries.

** But a TK_SELECT might be either a vector or a scalar. It is only

** considered a vector if it has two or more result columns.

*/

int sqlite3ExprIsVector(Expr *pExpr){

return sqlite3ExprVectorSize(pExpr)>1;

}

/*

** If the expression passed as the only argument is of type TK_VECTOR

** return the number of expressions in the vector. Or, if the expression

** is a sub-select, return the number of columns in the sub-select. For

** any other type of expression, return 1.

*/

int sqlite3ExprVectorSize(Expr *pExpr){

u8 op = pExpr->op;

if( op==TK_REGISTER ) op = pExpr->op2;

if( op==TK_VECTOR ){

return pExpr->x.pList->nExpr;

}else if( op==TK_SELECT ){

return pExpr->x.pSelect->pEList->nExpr;

}else{

return 1;

}

}

/*

** Return a pointer to a subexpression of pVector that is the i-th

** column of the vector (numbered starting with 0). The caller must

** ensure that i is within range.

**

** If pVector is really a scalar (and "scalar" here includes subqueries

** that return a single column!) then return pVector unmodified.

**

** pVector retains ownership of the returned subexpression.

**

** If the vector is a (SELECT ...) then the expression returned is

** just the expression for the i-th term of the result set, and may

** not be ready for evaluation because the table cursor has not yet

** been positioned.

*/

Expr *sqlite3VectorFieldSubexpr(Expr *pVector, int i){

assert( i<sqlite3ExprVectorSize(pVector) );

if( sqlite3ExprIsVector(pVector) ){

assert( pVector->op2==0 || pVector->op==TK_REGISTER );

if( pVector->op==TK_SELECT || pVector->op2==TK_SELECT ){

return pVector->x.pSelect->pEList->a[i].pExpr;

}else{

return pVector->x.pList->a[i].pExpr;

}

}

return pVector;

}

/*

** Compute and return a new Expr object which when passed to

** sqlite3ExprCode() will generate all necessary code to compute

** the iField-th column of the vector expression pVector.

**

** It is ok for pVector to be a scalar (as long as iField==0).

** In that case, this routine works like sqlite3ExprDup().

**

** The caller owns the returned Expr object and is responsible for

** ensuring that the returned value eventually gets freed.

**

** The caller retains ownership of pVector. If pVector is a TK_SELECT,

** then the returned object will reference pVector and so pVector must remain

** valid for the life of the returned object. If pVector is a TK_VECTOR

** or a scalar expression, then it can be deleted as soon as this routine

** returns.

**

** A trick to cause a TK_SELECT pVector to be deleted together with

** the returned Expr object is to attach the pVector to the pRight field

** of the returned TK_SELECT_COLUMN Expr object.

*/

Expr *sqlite3ExprForVectorField(

Parse *pParse, /* Parsing context */

Expr *pVector, /* The vector. List of expressions or a sub-SELECT */

int iField /* Which column of the vector to return */

){

Expr *pRet;

if( pVector->op==TK_SELECT ){

assert( pVector->flags & EP_xIsSelect );

/* The TK_SELECT_COLUMN Expr node:

**

** pLeft: pVector containing TK_SELECT. Not deleted.

** pRight: not used. But recursively deleted.

** iColumn: Index of a column in pVector

** iTable: 0 or the number of columns on the LHS of an assignment

** pLeft->iTable: First in an array of register holding result, or 0

** if the result is not yet computed.

**

** sqlite3ExprDelete() specifically skips the recursive delete of

** pLeft on TK_SELECT_COLUMN nodes. But pRight is followed, so pVector

** can be attached to pRight to cause this node to take ownership of

** pVector. Typically there will be multiple TK_SELECT_COLUMN nodes

** with the same pLeft pointer to the pVector, but only one of them

** will own the pVector.

*/

pRet = sqlite3PExpr(pParse, TK_SELECT_COLUMN, 0, 0);

if( pRet ){

pRet->iColumn = iField;

pRet->pLeft = pVector;

}

assert( pRet==0 || pRet->iTable==0 );

}else{

if( pVector->op==TK_VECTOR ) pVector = pVector->x.pList->a[iField].pExpr;

pRet = sqlite3ExprDup(pParse->db, pVector, 0);

}

return pRet;

}

/*

** If expression pExpr is of type TK_SELECT, generate code to evaluate

** it. Return the register in which the result is stored (or, if the

** sub-select returns more than one column, the first in an array

** of registers in which the result is stored).

**

** If pExpr is not a TK_SELECT expression, return 0.

*/

static int exprCodeSubselect(Parse *pParse, Expr *pExpr){

int reg = 0;

#ifndef SQLITE_OMIT_SUBQUERY

if( pExpr->op==TK_SELECT ){

reg = sqlite3CodeSubselect(pParse, pExpr, 0, 0);

}

#endif

return reg;

}

/*

** Argument pVector points to a vector expression - either a TK_VECTOR

** or TK_SELECT that returns more than one column. This function returns

** the register number of a register that contains the value of

** element iField of the vector.

**

** If pVector is a TK_SELECT expression, then code for it must have

** already been generated using the exprCodeSubselect() routine. In this

** case parameter regSelect should be the first in an array of registers

** containing the results of the sub-select.

**

** If pVector is of type TK_VECTOR, then code for the requested field

** is generated. In this case (*pRegFree) may be set to the number of

** a temporary register to be freed by the caller before returning.

**

** Before returning, output parameter (*ppExpr) is set to point to the

** Expr object corresponding to element iElem of the vector.

*/

static int exprVectorRegister(

Parse *pParse, /* Parse context */

Expr *pVector, /* Vector to extract element from */

int iField, /* Field to extract from pVector */

int regSelect, /* First in array of registers */

Expr **ppExpr, /* OUT: Expression element */

int *pRegFree /* OUT: Temp register to free */

){

u8 op = pVector->op;

assert( op==TK_VECTOR || op==TK_REGISTER || op==TK_SELECT );

if( op==TK_REGISTER ){

*ppExpr = sqlite3VectorFieldSubexpr(pVector, iField);

return pVector->iTable+iField;

}

if( op==TK_SELECT ){

*ppExpr = pVector->x.pSelect->pEList->a[iField].pExpr;

return regSelect+iField;

}

*ppExpr = pVector->x.pList->a[iField].pExpr;

return sqlite3ExprCodeTemp(pParse, *ppExpr, pRegFree);

}

/*

** Expression pExpr is a comparison between two vector values. Compute

** the result of the comparison (1, 0, or NULL) and write that

** result into register dest.

**

** The caller must satisfy the following preconditions:

**

** if pExpr->op==TK_IS: op==TK_EQ and p5==SQLITE_NULLEQ

** if pExpr->op==TK_ISNOT: op==TK_NE and p5==SQLITE_NULLEQ

** otherwise: op==pExpr->op and p5==0

*/

static void codeVectorCompare(

Parse *pParse, /* Code generator context */

Expr *pExpr, /* The comparison operation */

int dest, /* Write results into this register */

u8 op, /* Comparison operator */

u8 p5 /* SQLITE_NULLEQ or zero */

){

Vdbe *v = pParse->pVdbe;

Expr *pLeft = pExpr->pLeft;

Expr *pRight = pExpr->pRight;

int nLeft = sqlite3ExprVectorSize(pLeft);

int i;

int regLeft = 0;

int regRight = 0;

u8 opx = op;

int addrDone = sqlite3VdbeMakeLabel(v);

if( nLeft!=sqlite3ExprVectorSize(pRight) ){

sqlite3ErrorMsg(pParse, "row value misused");

return;

}

assert( pExpr->op==TK_EQ || pExpr->op==TK_NE

|| pExpr->op==TK_IS || pExpr->op==TK_ISNOT

|| pExpr->op==TK_LT || pExpr->op==TK_GT

|| pExpr->op==TK_LE || pExpr->op==TK_GE

);

assert( pExpr->op==op || (pExpr->op==TK_IS && op==TK_EQ)

|| (pExpr->op==TK_ISNOT && op==TK_NE) );

assert( p5==0 || pExpr->op!=op );

assert( p5==SQLITE_NULLEQ || pExpr->op==op );

p5 |= SQLITE_STOREP2;

if( opx==TK_LE ) opx = TK_LT;

if( opx==TK_GE ) opx = TK_GT;

regLeft = exprCodeSubselect(pParse, pLeft);

regRight = exprCodeSubselect(pParse, pRight);

for(i=0; 1 /*Loop exits by "break"*/; i++){

int regFree1 = 0, regFree2 = 0;

Expr *pL, *pR;

int r1, r2;

assert( i>=0 && i<nLeft );

r1 = exprVectorRegister(pParse, pLeft, i, regLeft, &pL, &regFree1);

r2 = exprVectorRegister(pParse, pRight, i, regRight, &pR, &regFree2);

codeCompare(pParse, pL, pR, opx, r1, r2, dest, p5);

testcase(op==OP_Lt); VdbeCoverageIf(v,op==OP_Lt);

testcase(op==OP_Le); VdbeCoverageIf(v,op==OP_Le);

testcase(op==OP_Gt); VdbeCoverageIf(v,op==OP_Gt);

testcase(op==OP_Ge); VdbeCoverageIf(v,op==OP_Ge);

testcase(op==OP_Eq); VdbeCoverageIf(v,op==OP_Eq);

testcase(op==OP_Ne); VdbeCoverageIf(v,op==OP_Ne);

sqlite3ReleaseTempReg(pParse, regFree1);

sqlite3ReleaseTempReg(pParse, regFree2);

if( i==nLeft-1 ){

break;

}

if( opx==TK_EQ ){

sqlite3VdbeAddOp2(v, OP_IfNot, dest, addrDone); VdbeCoverage(v);

p5 |= SQLITE_KEEPNULL;

}else if( opx==TK_NE ){

sqlite3VdbeAddOp2(v, OP_If, dest, addrDone); VdbeCoverage(v);

p5 |= SQLITE_KEEPNULL;

}else{

assert( op==TK_LT || op==TK_GT || op==TK_LE || op==TK_GE );

sqlite3VdbeAddOp2(v, OP_ElseNotEq, 0, addrDone);

VdbeCoverageIf(v, op==TK_LT);

VdbeCoverageIf(v, op==TK_GT);

VdbeCoverageIf(v, op==TK_LE);

VdbeCoverageIf(v, op==TK_GE);

if( i==nLeft-2 ) opx = op;

}

}

sqlite3VdbeResolveLabel(v, addrDone);

}

#if SQLITE_MAX_EXPR_DEPTH>0

/*

** Check that argument nHeight is less than or equal to the maximum

** expression depth allowed. If it is not, leave an error message in

** pParse.

*/

int sqlite3ExprCheckHeight(Parse *pParse, int nHeight){

int rc = SQLITE_OK;

int mxHeight = pParse->db->aLimit[SQLITE_LIMIT_EXPR_DEPTH];

if( nHeight>mxHeight ){

sqlite3ErrorMsg(pParse,

"Expression tree is too large (maximum depth %d)", mxHeight

);

rc = SQLITE_ERROR;

}

return rc;

}

/* The following three functions, heightOfExpr(), heightOfExprList()

** and heightOfSelect(), are used to determine the maximum height

** of any expression tree referenced by the structure passed as the

** first argument.

**

** If this maximum height is greater than the current value pointed

** to by pnHeight, the second parameter, then set *pnHeight to that

** value.

*/

static void heightOfExpr(Expr *p, int *pnHeight){

if( p ){

if( p->nHeight>*pnHeight ){

*pnHeight = p->nHeight;

}

}

}

static void heightOfExprList(ExprList *p, int *pnHeight){

if( p ){

int i;

for(i=0; i<p->nExpr; i++){

heightOfExpr(p->a[i].pExpr, pnHeight);

}

}

}

static void heightOfSelect(Select *pSelect, int *pnHeight){

Select *p;

for(p=pSelect; p; p=p->pPrior){

heightOfExpr(p->pWhere, pnHeight);

heightOfExpr(p->pHaving, pnHeight);

heightOfExpr(p->pLimit, pnHeight);

heightOfExprList(p->pEList, pnHeight);

heightOfExprList(p->pGroupBy, pnHeight);

heightOfExprList(p->pOrderBy, pnHeight);

}

}

/*

** Set the Expr.nHeight variable in the structure passed as an

** argument. An expression with no children, Expr.pList or

** Expr.pSelect member has a height of 1. Any other expression

** has a height equal to the maximum height of any other

** referenced Expr plus one.

**

** Also propagate EP_Propagate flags up from Expr.x.pList to Expr.flags,

** if appropriate.

*/

static void exprSetHeight(Expr *p){

int nHeight = 0;

heightOfExpr(p->pLeft, &nHeight);

heightOfExpr(p->pRight, &nHeight);

if( ExprHasProperty(p, EP_xIsSelect) ){

heightOfSelect(p->x.pSelect, &nHeight);

}else if( p->x.pList ){

heightOfExprList(p->x.pList, &nHeight);

p->flags |= EP_Propagate & sqlite3ExprListFlags(p->x.pList);

}

p->nHeight = nHeight + 1;

}

/*

** Set the Expr.nHeight variable using the exprSetHeight() function. If

** the height is greater than the maximum allowed expression depth,

** leave an error in pParse.

**

** Also propagate all EP_Propagate flags from the Expr.x.pList into

** Expr.flags.

*/

void sqlite3ExprSetHeightAndFlags(Parse *pParse, Expr *p){

if( pParse->nErr ) return;

exprSetHeight(p);

sqlite3ExprCheckHeight(pParse, p->nHeight);

}

/*

** Return the maximum height of any expression tree referenced

** by the select statement passed as an argument.

*/

int sqlite3SelectExprHeight(Select *p){

int nHeight = 0;

heightOfSelect(p, &nHeight);

return nHeight;

}

#else /* ABOVE: Height enforcement enabled. BELOW: Height enforcement off */

/*

** Propagate all EP_Propagate flags from the Expr.x.pList into

** Expr.flags.

*/

void sqlite3ExprSetHeightAndFlags(Parse *pParse, Expr *p){

if( p && p->x.pList && !ExprHasProperty(p, EP_xIsSelect) ){

p->flags |= EP_Propagate & sqlite3ExprListFlags(p->x.pList);

}

}

#define exprSetHeight(y)

#endif /* SQLITE_MAX_EXPR_DEPTH>0 */

/*

** This routine is the core allocator for Expr nodes.

**

** Construct a new expression node and return a pointer to it. Memory

** for this node and for the pToken argument is a single allocation

** obtained from sqlite3DbMalloc(). The calling function

** is responsible for making sure the node eventually gets freed.

**

** If dequote is true, then the token (if it exists) is dequoted.

** If dequote is false, no dequoting is performed. The deQuote

** parameter is ignored if pToken is NULL or if the token does not

** appear to be quoted. If the quotes were of the form "..." (double-quotes)

** then the EP_DblQuoted flag is set on the expression node.

**

** Special case: If op==TK_INTEGER and pToken points to a string that

** can be translated into a 32-bit integer, then the token is not

** stored in u.zToken. Instead, the integer values is written

** into u.iValue and the EP_IntValue flag is set. No extra storage

** is allocated to hold the integer text and the dequote flag is ignored.

*/

Expr *sqlite3ExprAlloc(

sqlite3 *db, /* Handle for sqlite3DbMallocRawNN() */

int op, /* Expression opcode */

const Token *pToken, /* Token argument. Might be NULL */

int dequote /* True to dequote */

){

Expr *pNew;

int nExtra = 0;

int iValue = 0;

assert( db!=0 );

if( pToken ){

if( op!=TK_INTEGER || pToken->z==0

|| sqlite3GetInt32(pToken->z, &iValue)==0 ){

nExtra = pToken->n+1;

assert( iValue>=0 );

}

}

pNew = sqlite3DbMallocRawNN(db, sizeof(Expr)+nExtra);

if( pNew ){

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

pNew->op = (u8)op;

pNew->iAgg = -1;

if( pToken ){

if( nExtra==0 ){

pNew->flags |= EP_IntValue|EP_Leaf;

pNew->u.iValue = iValue;

}else{

pNew->u.zToken = (char*)&pNew[1];

assert( pToken->z!=0 || pToken->n==0 );

if( pToken->n ) memcpy(pNew->u.zToken, pToken->z, pToken->n);

pNew->u.zToken[pToken->n] = 0;

if( dequote && sqlite3Isquote(pNew->u.zToken[0]) ){

if( pNew->u.zToken[0]=='"' ) pNew->flags |= EP_DblQuoted;

sqlite3Dequote(pNew->u.zToken);

}

}

}

#if SQLITE_MAX_EXPR_DEPTH>0

pNew->nHeight = 1;

#endif

}

return pNew;

}

/*

** Allocate a new expression node from a zero-terminated token that has

** already been dequoted.

*/

Expr *sqlite3Expr(

sqlite3 *db, /* Handle for sqlite3DbMallocZero() (may be null) */

int op, /* Expression opcode */

const char *zToken /* Token argument. Might be NULL */

){

Token x;

x.z = zToken;

x.n = sqlite3Strlen30(zToken);

return sqlite3ExprAlloc(db, op, &x, 0);

}

/*

** Attach subtrees pLeft and pRight to the Expr node pRoot.

**

** If pRoot==NULL that means that a memory allocation error has occurred.

** In that case, delete the subtrees pLeft and pRight.

*/

void sqlite3ExprAttachSubtrees(

sqlite3 *db,

Expr *pRoot,

Expr *pLeft,

Expr *pRight

){

if( pRoot==0 ){

assert( db->mallocFailed );

sqlite3ExprDelete(db, pLeft);

sqlite3ExprDelete(db, pRight);

}else{

if( pRight ){

pRoot->pRight = pRight;

pRoot->flags |= EP_Propagate & pRight->flags;

}

if( pLeft ){

pRoot->pLeft = pLeft;

pRoot->flags |= EP_Propagate & pLeft->flags;

}

exprSetHeight(pRoot);

}

}

/*

** Allocate an Expr node which joins as many as two subtrees.

**

** One or both of the subtrees can be NULL. Return a pointer to the new

** Expr node. Or, if an OOM error occurs, set pParse->db->mallocFailed,

** free the subtrees and return NULL.

*/

Expr *sqlite3PExpr(

Parse *pParse, /* Parsing context */

int op, /* Expression opcode */

Expr *pLeft, /* Left operand */

Expr *pRight /* Right operand */

){

Expr *p;

if( op==TK_AND && pParse->nErr==0 ){

/* Take advantage of short-circuit false optimization for AND */

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

}else{

p = sqlite3DbMallocRawNN(pParse->db, sizeof(Expr));

if( p ){

memset(p, 0, sizeof(Expr));

p->op = op & TKFLG_MASK;

p->iAgg = -1;

}

sqlite3ExprAttachSubtrees(pParse->db, p, pLeft, pRight);

}

if( p ) {

sqlite3ExprCheckHeight(pParse, p->nHeight);

}

return p;

}

/*

** Add pSelect to the Expr.x.pSelect field. Or, if pExpr is NULL (due

** do a memory allocation failure) then delete the pSelect object.

*/

void sqlite3PExprAddSelect(Parse *pParse, Expr *pExpr, Select *pSelect){

if( pExpr ){

pExpr->x.pSelect = pSelect;

ExprSetProperty(pExpr, EP_xIsSelect|EP_Subquery);

sqlite3ExprSetHeightAndFlags(pParse, pExpr);

}else{

assert( pParse->db->mallocFailed );

sqlite3SelectDelete(pParse->db, pSelect);

}

}

/*

** If the expression is always either TRUE or FALSE (respectively),

** then return 1. If one cannot determine the truth value of the

** expression at compile-time return 0.

**

** This is an optimization. If is OK to return 0 here even if

** the expression really is always false or false (a false negative).

** But it is a bug to return 1 if the expression might have different

** boolean values in different circumstances (a false positive.)

**

** Note that if the expression is part of conditional for a

** LEFT JOIN, then we cannot determine at compile-time whether or not

** is it true or false, so always return 0.

*/

static int exprAlwaysTrue(Expr *p){

int v = 0;

if( ExprHasProperty(p, EP_FromJoin) ) return 0;

if( !sqlite3ExprIsInteger(p, &v) ) return 0;

return v!=0;

}

static int exprAlwaysFalse(Expr *p){

int v = 0;

if( ExprHasProperty(p, EP_FromJoin) ) return 0;

if( !sqlite3ExprIsInteger(p, &v) ) return 0;

return v==0;

}

/*

** Join two expressions using an AND operator. If either expression is

** NULL, then just return the other expression.

**

** If one side or the other of the AND is known to be false, then instead

** of returning an AND expression, just return a constant expression with

** a value of false.

*/

Expr *sqlite3ExprAnd(sqlite3 *db, Expr *pLeft, Expr *pRight){

if( pLeft==0 ){

return pRight;

}else if( pRight==0 ){

return pLeft;

}else if( exprAlwaysFalse(pLeft) || exprAlwaysFalse(pRight) ){

sqlite3ExprDelete(db, pLeft);

sqlite3ExprDelete(db, pRight);

return sqlite3ExprAlloc(db, TK_INTEGER, &sqlite3IntTokens[0], 0);

}else{

Expr *pNew = sqlite3ExprAlloc(db, TK_AND, 0, 0);

sqlite3ExprAttachSubtrees(db, pNew, pLeft, pRight);

return pNew;

}

}

/*

** Construct a new expression node for a function with multiple

** arguments.

*/

Expr *sqlite3ExprFunction(

Parse *pParse, /* Parsing context */

ExprList *pList, /* Argument list */

Token *pToken, /* Name of the function */

int eDistinct /* SF_Distinct or SF_ALL or 0 */

){

Expr *pNew;

sqlite3 *db = pParse->db;

assert( pToken );

pNew = sqlite3ExprAlloc(db, TK_FUNCTION, pToken, 1);

if( pNew==0 ){

sqlite3ExprListDelete(db, pList); /* Avoid memory leak when malloc fails */

return 0;

}

if( pList && pList->nExpr > pParse->db->aLimit[SQLITE_LIMIT_FUNCTION_ARG] ){

sqlite3ErrorMsg(pParse, "too many arguments on function %T", pToken);

}

pNew->x.pList = pList;

ExprSetProperty(pNew, EP_HasFunc);

assert( !ExprHasProperty(pNew, EP_xIsSelect) );

sqlite3ExprSetHeightAndFlags(pParse, pNew);

if( eDistinct==SF_Distinct ) ExprSetProperty(pNew, EP_Distinct);

return pNew;

}

/*

** Assign a variable number to an expression that encodes a wildcard

** in the original SQL statement.

**

** Wildcards consisting of a single "?" are assigned the next sequential

** variable number.

**

** Wildcards of the form "?nnn" are assigned the number "nnn". We make

** sure "nnn" is not too big to avoid a denial of service attack when

** the SQL statement comes from an external source.

**

** Wildcards of the form ":aaa", "@aaa", or "$aaa" are assigned the same number

** as the previous instance of the same wildcard. Or if this is the first

** instance of the wildcard, the next sequential variable number is

** assigned.

*/

void sqlite3ExprAssignVarNumber(Parse *pParse, Expr *pExpr, u32 n){

sqlite3 *db = pParse->db;

const char *z;

ynVar x;

if( pExpr==0 ) return;

assert( !ExprHasProperty(pExpr, EP_IntValue|EP_Reduced|EP_TokenOnly) );

z = pExpr->u.zToken;

assert( z!=0 );

assert( z[0]!=0 );

assert( n==(u32)sqlite3Strlen30(z) );

if( z[1]==0 ){

/* Wildcard of the form "?". Assign the next variable number */

assert( z[0]=='?' );

x = (ynVar)(++pParse->nVar);

}else{

int doAdd = 0;

if( z[0]=='?' ){