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