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, &regFree1);
000558      r2 = exprVectorRegister(pParse, pRight, i, regRight, &pR, &regFree2);
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, &regToFree);
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, &regFree1);
003467          r2 = sqlite3ExprCodeTemp(pParse, pExpr->pRight, &regFree2);
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, &regFree1);
003505        r2 = sqlite3ExprCodeTemp(pParse, pExpr->pRight, &regFree2);
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, &regFree1);
003528          r2 = sqlite3ExprCodeTemp(pParse, pExpr->pLeft, &regFree2);
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, &regFree1);
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, &regFree1);
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, &regFree1));
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, &regFree1));
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, &regFree1);
004273        r2 = sqlite3ExprCodeTemp(pParse, pExpr->pRight, &regFree2);
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, &regFree1);
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, &regFree1);
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, &regFree1);
004427        r2 = sqlite3ExprCodeTemp(pParse, pExpr->pRight, &regFree2);
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, &regFree1);
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, &regFree1);
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 */