/*

** 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"

/*

** 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 expresssions 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);

op = pExpr->op;

if( op==TK_SELECT ){

assert( pExpr->flags&EP_xIsSelect );

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

}

#ifndef SQLITE_OMIT_CAST

if( op==TK_CAST ){

assert( !ExprHasProperty(pExpr, EP_IntValue) );

return sqlite3AffinityType(pExpr->u.zToken);

}

#endif

if( (op==TK_AGG_COLUMN || op==TK_COLUMN || op==TK_REGISTER)

&& pExpr->pTab!=0

){

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

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

int j = pExpr->iColumn;

if( j<0 ) return SQLITE_AFF_INTEGER;

assert( pExpr->pTab && j<pExpr->pTab->nCol );

return pExpr->pTab->aCol[j].affinity;

}

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, Expr *pExpr, Token *pCollName){

if( pCollName->n>0 ){

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

if( pNew ){

pNew->pLeft = pExpr;

pNew->flags |= EP_Collate;

pExpr = pNew;

}

}

return pExpr;

}

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

Token s;

assert( zC!=0 );

s.z = zC;

s.n = sqlite3Strlen30(s.z);

return sqlite3ExprAddCollateToken(pParse, pExpr, &s);

}

/*

** Skip over any TK_COLLATE and/or TK_AS operators at the root of

** an expression.

*/

Expr *sqlite3ExprSkipCollate(Expr *pExpr){

while( pExpr && (pExpr->op==TK_COLLATE || pExpr->op==TK_AS) ){

pExpr = pExpr->pLeft;

}

return pExpr;

}

/*

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

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

**

** 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( 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->pTab!=0

&& (op==TK_AGG_COLUMN || op==TK_COLUMN

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

){

/* op==TK_REGISTER && p->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->pTab->aCol[j].zColl;

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

}

break;

}

if( p->flags & EP_Collate ){

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

p = p->pLeft;

}else{

p = p->pRight;

}

}else{

break;

}

}

if( sqlite3CheckCollSeq(pParse, pColl) ){

pColl = 0;

}

return pColl;

}

/*

** 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_NONE;

}

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

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

** results directly.

*/

return SQLITE_AFF_NONE;

}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 ){

aff = SQLITE_AFF_NONE;

}

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_NONE:

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;

}

#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 *p, int *pnHeight){

if( p ){

heightOfExpr(p->pWhere, pnHeight);

heightOfExpr(p->pHaving, pnHeight);

heightOfExpr(p->pLimit, pnHeight);

heightOfExpr(p->pOffset, pnHeight);

heightOfExprList(p->pEList, pnHeight);

heightOfExprList(p->pGroupBy, pnHeight);

heightOfExprList(p->pOrderBy, pnHeight);

heightOfSelect(p->pPrior, 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.

*/

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{

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

}

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.

*/

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

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

#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 performance. 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 sqlite3DbMallocZero() (may be null) */

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;

if( pToken ){

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

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

nExtra = pToken->n+1;

assert( iValue>=0 );

}

}

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

if( pNew ){

pNew->op = (u8)op;

pNew->iAgg = -1;

if( pToken ){

if( nExtra==0 ){

pNew->flags |= EP_IntValue;

pNew->u.iValue = iValue;

}else{

int c;

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 && nExtra>=3

&& ((c = pToken->z[0])=='\'' || c=='"' || c=='[' || c=='`') ){

sqlite3Dequote(pNew->u.zToken);

if( c=='"' ) pNew->flags |= EP_DblQuoted;

}

}

}

#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 = zToken ? sqlite3Strlen30(zToken) : 0;

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_Collate & pRight->flags;

}

if( pLeft ){

pRoot->pLeft = pLeft;

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

}

exprSetHeight(pRoot);

}

}

/*

** Allocate a 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 */

const Token *pToken /* Argument token */

){

Expr *p;

if( op==TK_AND && pLeft && pRight ){

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

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

}else{

p = sqlite3ExprAlloc(pParse->db, op, pToken, 1);

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

}

if( p ) {

sqlite3ExprCheckHeight(pParse, p->nHeight);

}

return p;

}

/*

** Return 1 if an expression must be FALSE in all cases and 0 if the

** expression might be true. This is an optimization. If is OK to

** return 0 here even if the expression really is always false (a

** false negative). But it is a bug to return 1 if the expression

** might be true in some rare 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 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, ExprList *pList, Token *pToken){

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;

}

pNew->x.pList = pList;

assert( !ExprHasProperty(pNew, EP_xIsSelect) );

sqlite3ExprSetHeight(pParse, pNew);

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 be 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 sequenial variable number is

** assigned.

*/

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

sqlite3 *db = pParse->db;

const char *z;

if( pExpr==0 ) return;

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

z = pExpr->u.zToken;

assert( z!=0 );

assert( z[0]!=0 );

if( z[1]==0 ){

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

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

pExpr->iColumn = (ynVar)(++pParse->nVar);

}else{

ynVar x = 0;

u32 n = sqlite3Strlen30(z);

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

/* Wildcard of the form "?nnn". Convert "nnn" to an integer and

** use it as the variable number */

i64 i;

int bOk = 0==sqlite3Atoi64(&z[1], &i, n-1, SQLITE_UTF8);

pExpr->iColumn = x = (ynVar)i;

testcase( i==0 );

testcase( i==1 );

testcase( i==db->aLimit[SQLITE_LIMIT_VARIABLE_NUMBER]-1 );

testcase( i==db->aLimit[SQLITE_LIMIT_VARIABLE_NUMBER] );

if( bOk==0 || i<1 || i>db->aLimit[SQLITE_LIMIT_VARIABLE_NUMBER] ){

sqlite3ErrorMsg(pParse, "variable number must be between ?1 and ?%d",

db->aLimit[SQLITE_LIMIT_VARIABLE_NUMBER]);

x = 0;

}

if( i>pParse->nVar ){

pParse->nVar = (int)i;

}

}else{

/* Wildcards like ":aaa", "$aaa" or "@aaa". Reuse the same variable

** number as the prior appearance of the same name, or if the name

** has never appeared before, reuse the same variable number

*/

ynVar i;

for(i=0; i<pParse->nzVar; i++){

if( pParse->azVar[i] && strcmp(pParse->azVar[i],z)==0 ){

pExpr->iColumn = x = (ynVar)i+1;

break;

}

}

if( x==0 ) x = pExpr->iColumn = (ynVar)(++pParse->nVar);

}

if( x>0 ){

if( x>pParse->nzVar ){

char **a;

a = sqlite3DbRealloc(db, pParse->azVar, x*sizeof(a[0]));

if( a==0 ) return; /* Error reported through db->mallocFailed */

pParse->azVar = a;

memset(&a[pParse->nzVar], 0, (x-pParse->nzVar)*sizeof(a[0]));

pParse->nzVar = x;

}

if( z[0]!='?' || pParse->azVar[x-1]==0 ){

sqlite3DbFree(db, pParse->azVar[x-1]);

pParse->azVar[x-1] = sqlite3DbStrNDup(db, z, n);

}

}

}

if( !pParse->nErr && pParse->nVar>db->aLimit[SQLITE_LIMIT_VARIABLE_NUMBER] ){

sqlite3ErrorMsg(pParse, "too many SQL variables");

}

}

/*

** Recursively delete an expression tree.

*/

void sqlite3ExprDelete(sqlite3 *db, Expr *p){

if( p==0 ) return;

/* Sanity check: Assert that the IntValue is non-negative if it exists */

assert( !ExprHasProperty(p, EP_IntValue) || p->u.iValue>=0 );

if( !ExprHasAnyProperty(p, EP_TokenOnly) ){

sqlite3ExprDelete(db, p->pLeft);

sqlite3ExprDelete(db, p->pRight);

if( !ExprHasProperty(p, EP_Reduced) && (p->flags2 & EP2_MallocedToken)!=0 ){

sqlite3DbFree(db, p->u.zToken);

}

if( ExprHasProperty(p, EP_xIsSelect) ){

sqlite3SelectDelete(db, p->x.pSelect);

}else{

sqlite3ExprListDelete(db, p->x.pList);

}

}

if( !ExprHasProperty(p, EP_Static) ){

sqlite3DbFree(db, p);

}

}

/*

** Return the number of bytes allocated for the expression structure

** passed as the first argument. This is always one of EXPR_FULLSIZE,

** EXPR_REDUCEDSIZE or EXPR_TOKENONLYSIZE.

*/

static int exprStructSize(Expr *p){

if( ExprHasProperty(p, EP_TokenOnly) ) return EXPR_TOKENONLYSIZE;

if( ExprHasProperty(p, EP_Reduced) ) return EXPR_REDUCEDSIZE;

return EXPR_FULLSIZE;

}

/*

** The dupedExpr*Size() routines each return the number of bytes required

** to store a copy of an expression or expression tree. They differ in

** how much of the tree is measured.

**

** dupedExprStructSize() Size of only the Expr structure

** dupedExprNodeSize() Size of Expr + space for token

** dupedExprSize() Expr + token + subtree components

**

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

**

** The dupedExprStructSize() function returns two values OR-ed together:

** (1) the space required for a copy of the Expr structure only and

** (2) the EP_xxx flags that indicate what the structure size should be.

** The return values is always one of:

**

** EXPR_FULLSIZE

** EXPR_REDUCEDSIZE | EP_Reduced

** EXPR_TOKENONLYSIZE | EP_TokenOnly

**

** The size of the structure can be found by masking the return value

** of this routine with 0xfff. The flags can be found by masking the

** return value with EP_Reduced|EP_TokenOnly.

**

** Note that with flags==EXPRDUP_REDUCE, this routines works on full-size

** (unreduced) Expr objects as they or originally constructed by the parser.

** During expression analysis, extra information is computed and moved into

** later parts of teh Expr object and that extra information might get chopped

** off if the expression is reduced. Note also that it does not work to

** make a EXPRDUP_REDUCE copy of a reduced expression. It is only legal

** to reduce a pristine expression tree from the parser. The implementation

** of dupedExprStructSize() contain multiple assert() statements that attempt

** to enforce this constraint.

*/

static int dupedExprStructSize(Expr *p, int flags){

int nSize;

assert( flags==EXPRDUP_REDUCE || flags==0 ); /* Only one flag value allowed */

if( 0==(flags&EXPRDUP_REDUCE) ){

nSize = EXPR_FULLSIZE;

}else{

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

assert( !ExprHasProperty(p, EP_FromJoin) );

assert( (p->flags2 & EP2_MallocedToken)==0 );

assert( (p->flags2 & EP2_Irreducible)==0 );

if( p->pLeft || p->pRight || p->x.pList ){

nSize = EXPR_REDUCEDSIZE | EP_Reduced;

}else{

nSize = EXPR_TOKENONLYSIZE | EP_TokenOnly;

}

}

return nSize;

}

/*

** This function returns the space in bytes required to store the copy

** of the Expr structure and a copy of the Expr.u.zToken string (if that

** string is defined.)

*/

static int dupedExprNodeSize(Expr *p, int flags){

int nByte = dupedExprStructSize(p, flags) & 0xfff;

if( !ExprHasProperty(p, EP_IntValue) && p->u.zToken ){

nByte += sqlite3Strlen30(p->u.zToken)+1;

}

return ROUND8(nByte);

}

/*

** Return the number of bytes required to create a duplicate of the

** expression passed as the first argument. The second argument is a

** mask containing EXPRDUP_XXX flags.

**

** The value returned includes space to create a copy of the Expr struct

** itself and the buffer referred to by Expr.u.zToken, if any.

**

** If the EXPRDUP_REDUCE flag is set, then the return value includes

** space to duplicate all Expr nodes in the tree formed by Expr.pLeft

** and Expr.pRight variables (but not for any structures pointed to or

** descended from the Expr.x.pList or Expr.x.pSelect variables).

*/

static int dupedExprSize(Expr *p, int flags){

int nByte = 0;

if( p ){

nByte = dupedExprNodeSize(p, flags);

if( flags&EXPRDUP_REDUCE ){

nByte += dupedExprSize(p->pLeft, flags) + dupedExprSize(p->pRight, flags);

}

}

return nByte;

}

/*

** This function is similar to sqlite3ExprDup(), except that if pzBuffer

** is not NULL then *pzBuffer is assumed to point to a buffer large enough

** to store the copy of expression p, the copies of p->u.zToken

** (if applicable), and the copies of the p->pLeft and p->pRight expressions,

** if any. Before returning, *pzBuffer is set to the first byte passed the

** portion of the buffer copied into by this function.

*/

static Expr *exprDup(sqlite3 *db, Expr *p, int flags, u8 **pzBuffer){

Expr *pNew = 0; /* Value to return */

if( p ){

const int isReduced = (flags&EXPRDUP_REDUCE);

u8 *zAlloc;

u32 staticFlag = 0;

assert( pzBuffer==0 || isReduced );

/* Figure out where to write the new Expr structure. */

if( pzBuffer ){

zAlloc = *pzBuffer;

staticFlag = EP_Static;

}else{

zAlloc = sqlite3DbMallocRaw(db, dupedExprSize(p, flags));

}

pNew = (Expr *)zAlloc;

if( pNew ){

/* Set nNewSize to the size allocated for the structure pointed to

** by pNew. This is either EXPR_FULLSIZE, EXPR_REDUCEDSIZE or

** EXPR_TOKENONLYSIZE. nToken is set to the number of bytes consumed

** by the copy of the p->u.zToken string (if any).

*/

const unsigned nStructSize = dupedExprStructSize(p, flags);

const int nNewSize = nStructSize & 0xfff;

int nToken;

if( !ExprHasProperty(p, EP_IntValue) && p->u.zToken ){

nToken = sqlite3Strlen30(p->u.zToken) + 1;

}else{

nToken = 0;

}

if( isReduced ){

assert( ExprHasProperty(p, EP_Reduced)==0 );

memcpy(zAlloc, p, nNewSize);

}else{

int nSize = exprStructSize(p);

memcpy(zAlloc, p, nSize);

memset(&zAlloc[nSize], 0, EXPR_FULLSIZE-nSize);

}

/* Set the EP_Reduced, EP_TokenOnly, and EP_Static flags appropriately. */

pNew->flags &= ~(EP_Reduced|EP_TokenOnly|EP_Static);

pNew->flags |= nStructSize & (EP_Reduced|EP_TokenOnly);

pNew->flags |= staticFlag;

/* Copy the p->u.zToken string, if any. */

if( nToken ){

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

memcpy(zToken, p->u.zToken, nToken);

}

if( 0==((p->flags|pNew->flags) & EP_TokenOnly) ){

/* Fill in the pNew->x.pSelect or pNew->x.pList member. */

if( ExprHasProperty(p, EP_xIsSelect) ){

pNew->x.pSelect = sqlite3SelectDup(db, p->x.pSelect, isReduced);

}else{

pNew->x.pList = sqlite3ExprListDup(db, p->x.pList, isReduced);

}

}

/* Fill in pNew->pLeft and pNew->pRight. */

if( ExprHasAnyProperty(pNew, EP_Reduced|EP_TokenOnly) ){

zAlloc += dupedExprNodeSize(p, flags);

if( ExprHasProperty(pNew, EP_Reduced) ){

pNew->pLeft = exprDup(db, p->pLeft, EXPRDUP_REDUCE, &zAlloc);

pNew->pRight = exprDup(db, p->pRight, EXPRDUP_REDUCE, &zAlloc);

}

if( pzBuffer ){

*pzBuffer = zAlloc;

}

}else{

pNew->flags2 = 0;

if( !ExprHasAnyProperty(p, EP_TokenOnly) ){

pNew->pLeft = sqlite3ExprDup(db, p->pLeft, 0);

pNew->pRight = sqlite3ExprDup(db, p->pRight, 0);

}

}

}

}

return pNew;

}

/*

** The following group of routines make deep copies of expressions,

** expression lists, ID lists, and select statements. The copies can

** be deleted (by being passed to their respective ...Delete() routines)

** without effecting the originals.

**

** The expression list, ID, and source lists return by sqlite3ExprListDup(),

** sqlite3IdListDup(), and sqlite3SrcListDup() can not be further expanded

** by subsequent calls to sqlite*ListAppend() routines.

**

** Any tables that the SrcList might point to are not duplicated.

**

** The flags parameter contains a combination of the EXPRDUP_XXX flags.

** If the EXPRDUP_REDUCE flag is set, then the structure returned is a

** truncated version of the usual Expr structure that will be stored as

** part of the in-memory representation of the database schema.

*/

Expr *sqlite3ExprDup(sqlite3 *db, Expr *p, int flags){

return exprDup(db, p, flags, 0);

}

ExprList *sqlite3ExprListDup(sqlite3 *db, ExprList *p, int flags){

ExprList *pNew;

struct ExprList_item *pItem, *pOldItem;

int i;

if( p==0 ) return 0;

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

if( pNew==0 ) return 0;

pNew->iECursor = 0;

pNew->nExpr = i = p->nExpr;

if( (flags & EXPRDUP_REDUCE)==0 ) for(i=1; i<p->nExpr; i+=i){}

pNew->a = pItem = sqlite3DbMallocRaw(db, i*sizeof(p->a[0]) );

if( pItem==0 ){

sqlite3DbFree(db, pNew);

return 0;

}

pOldItem = p->a;

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

Expr *pOldExpr = pOldItem->pExpr;

pItem->pExpr = sqlite3ExprDup(db, pOldExpr, flags);

pItem->zName = sqlite3DbStrDup(db, pOldItem->zName);

pItem->zSpan = sqlite3DbStrDup(db, pOldItem->zSpan);

pItem->sortOrder = pOldItem->sortOrder;

pItem->done = 0;

pItem->bSpanIsTab = pOldItem->bSpanIsTab;

pItem->iOrderByCol = pOldItem->iOrderByCol;

pItem->iAlias = pOldItem->iAlias;

}

return pNew;

}

/*

** If cursors, triggers, views and subqueries are all omitted from

** the build, then none of the following routines, except for

** sqlite3SelectDup(), can be called. sqlite3SelectDup() is sometimes

** called with a NULL argument.

*/

#if !defined(SQLITE_OMIT_VIEW) || !defined(SQLITE_OMIT_TRIGGER) \

|| !defined(SQLITE_OMIT_SUBQUERY)

SrcList *sqlite3SrcListDup(sqlite3 *db, SrcList *p, int flags){

SrcList *pNew;

int i;

int nByte;

if( p==0 ) return 0;

nByte = sizeof(*p) + (p->nSrc>0 ? sizeof(p->a[0]) * (p->nSrc-1) : 0);

pNew = sqlite3DbMallocRaw(db, nByte );

if( pNew==0 ) return 0;

pNew->nSrc = pNew->nAlloc = p->nSrc;

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

struct SrcList_item *pNewItem = &pNew->a[i];

struct SrcList_item *pOldItem = &p->a[i];

Table *pTab;

pNewItem->pSchema = pOldItem->pSchema;

pNewItem->zDatabase = sqlite3DbStrDup(db, pOldItem->zDatabase);

pNewItem->zName = sqlite3DbStrDup(db, pOldItem->zName);

pNewItem->zAlias = sqlite3DbStrDup(db, pOldItem->zAlias);

pNewItem->jointype = pOldItem->jointype;

pNewItem->iCursor = pOldItem->iCursor;

pNewItem->addrFillSub = pOldItem->addrFillSub;

pNewItem->regReturn = pOldItem->regReturn;

pNewItem->isCorrelated = pOldItem->isCorrelated;

pNewItem->viaCoroutine = pOldItem->viaCoroutine;

pNewItem->zIndex = sqlite3DbStrDup(db, pOldItem->zIndex);

pNewItem->notIndexed = pOldItem->notIndexed;

pNewItem->pIndex = pOldItem->pIndex;

pTab = pNewItem->pTab = pOldItem->pTab;

if( pTab ){

pTab->nRef++;

}

pNewItem->pSelect = sqlite3SelectDup(db, pOldItem->pSelect, flags);

pNewItem->pOn = sqlite3ExprDup(db, pOldItem->pOn, flags);

pNewItem->pUsing = sqlite3IdListDup(db, pOldItem->pUsing);

pNewItem->colUsed = pOldItem->colUsed;

}

return pNew;

}

IdList *sqlite3IdListDup(sqlite3 *db, IdList *p){

IdList *pNew;

int i;

if( p==0 ) return 0;

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

if( pNew==0 ) return 0;

pNew->nId = p->nId;

pNew->a = sqlite3DbMallocRaw(db, p->nId*sizeof(p->a[0]) );

if( pNew->a==0 ){

sqlite3DbFree(db, pNew);

return 0;

}

/* Note that because the size of the allocation for p->a[] is not

** necessarily a power of two, sqlite3IdListAppend() may not be called

** on the duplicate created by this function. */

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

struct IdList_item *pNewItem = &pNew->a[i];

struct IdList_item *pOldItem = &p->a[i];

pNewItem->zName = sqlite3DbStrDup(db, pOldItem->zName);

pNewItem->idx = pOldItem->idx;

}

return pNew;

}

Select *sqlite3SelectDup(sqlite3 *db, Select *p, int flags){

Select *pNew, *pPrior;

if( p==0 ) return 0;

pNew = sqlite3DbMallocRaw(db, sizeof(*p) );