000001  /*
000002  ** 2008 August 18
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  **
000013  ** This file contains routines used for walking the parser tree and
000014  ** resolve all identifiers by associating them with a particular
000015  ** table and column.
000016  */
000017  #include "sqliteInt.h"
000018  
000019  /*
000020  ** Walk the expression tree pExpr and increase the aggregate function
000021  ** depth (the Expr.op2 field) by N on every TK_AGG_FUNCTION node.
000022  ** This needs to occur when copying a TK_AGG_FUNCTION node from an
000023  ** outer query into an inner subquery.
000024  **
000025  ** incrAggFunctionDepth(pExpr,n) is the main routine.  incrAggDepth(..)
000026  ** is a helper function - a callback for the tree walker.
000027  */
000028  static int incrAggDepth(Walker *pWalker, Expr *pExpr){
000029    if( pExpr->op==TK_AGG_FUNCTION ) pExpr->op2 += pWalker->u.n;
000030    return WRC_Continue;
000031  }
000032  static void incrAggFunctionDepth(Expr *pExpr, int N){
000033    if( N>0 ){
000034      Walker w;
000035      memset(&w, 0, sizeof(w));
000036      w.xExprCallback = incrAggDepth;
000037      w.u.n = N;
000038      sqlite3WalkExpr(&w, pExpr);
000039    }
000040  }
000041  
000042  /*
000043  ** Turn the pExpr expression into an alias for the iCol-th column of the
000044  ** result set in pEList.
000045  **
000046  ** If the reference is followed by a COLLATE operator, then make sure
000047  ** the COLLATE operator is preserved.  For example:
000048  **
000049  **     SELECT a+b, c+d FROM t1 ORDER BY 1 COLLATE nocase;
000050  **
000051  ** Should be transformed into:
000052  **
000053  **     SELECT a+b, c+d FROM t1 ORDER BY (a+b) COLLATE nocase;
000054  **
000055  ** The nSubquery parameter specifies how many levels of subquery the
000056  ** alias is removed from the original expression.  The usual value is
000057  ** zero but it might be more if the alias is contained within a subquery
000058  ** of the original expression.  The Expr.op2 field of TK_AGG_FUNCTION
000059  ** structures must be increased by the nSubquery amount.
000060  */
000061  static void resolveAlias(
000062    Parse *pParse,         /* Parsing context */
000063    ExprList *pEList,      /* A result set */
000064    int iCol,              /* A column in the result set.  0..pEList->nExpr-1 */
000065    Expr *pExpr,           /* Transform this into an alias to the result set */
000066    const char *zType,     /* "GROUP" or "ORDER" or "" */
000067    int nSubquery          /* Number of subqueries that the label is moving */
000068  ){
000069    Expr *pOrig;           /* The iCol-th column of the result set */
000070    Expr *pDup;            /* Copy of pOrig */
000071    sqlite3 *db;           /* The database connection */
000072  
000073    assert( iCol>=0 && iCol<pEList->nExpr );
000074    pOrig = pEList->a[iCol].pExpr;
000075    assert( pOrig!=0 );
000076    db = pParse->db;
000077    pDup = sqlite3ExprDup(db, pOrig, 0);
000078    if( pDup!=0 ){
000079      if( zType[0]!='G' ) incrAggFunctionDepth(pDup, nSubquery);
000080      if( pExpr->op==TK_COLLATE ){
000081        pDup = sqlite3ExprAddCollateString(pParse, pDup, pExpr->u.zToken);
000082      }
000083      ExprSetProperty(pDup, EP_Alias);
000084  
000085      /* Before calling sqlite3ExprDelete(), set the EP_Static flag. This 
000086      ** prevents ExprDelete() from deleting the Expr structure itself,
000087      ** allowing it to be repopulated by the memcpy() on the following line.
000088      ** The pExpr->u.zToken might point into memory that will be freed by the
000089      ** sqlite3DbFree(db, pDup) on the last line of this block, so be sure to
000090      ** make a copy of the token before doing the sqlite3DbFree().
000091      */
000092      ExprSetProperty(pExpr, EP_Static);
000093      sqlite3ExprDelete(db, pExpr);
000094      memcpy(pExpr, pDup, sizeof(*pExpr));
000095      if( !ExprHasProperty(pExpr, EP_IntValue) && pExpr->u.zToken!=0 ){
000096        assert( (pExpr->flags & (EP_Reduced|EP_TokenOnly))==0 );
000097        pExpr->u.zToken = sqlite3DbStrDup(db, pExpr->u.zToken);
000098        pExpr->flags |= EP_MemToken;
000099      }
000100      sqlite3DbFree(db, pDup);
000101    }
000102    ExprSetProperty(pExpr, EP_Alias);
000103  }
000104  
000105  
000106  /*
000107  ** Return TRUE if the name zCol occurs anywhere in the USING clause.
000108  **
000109  ** Return FALSE if the USING clause is NULL or if it does not contain
000110  ** zCol.
000111  */
000112  static int nameInUsingClause(IdList *pUsing, const char *zCol){
000113    if( pUsing ){
000114      int k;
000115      for(k=0; k<pUsing->nId; k++){
000116        if( sqlite3StrICmp(pUsing->a[k].zName, zCol)==0 ) return 1;
000117      }
000118    }
000119    return 0;
000120  }
000121  
000122  /*
000123  ** Subqueries stores the original database, table and column names for their
000124  ** result sets in ExprList.a[].zSpan, in the form "DATABASE.TABLE.COLUMN".
000125  ** Check to see if the zSpan given to this routine matches the zDb, zTab,
000126  ** and zCol.  If any of zDb, zTab, and zCol are NULL then those fields will
000127  ** match anything.
000128  */
000129  int sqlite3MatchSpanName(
000130    const char *zSpan,
000131    const char *zCol,
000132    const char *zTab,
000133    const char *zDb
000134  ){
000135    int n;
000136    for(n=0; ALWAYS(zSpan[n]) && zSpan[n]!='.'; n++){}
000137    if( zDb && (sqlite3StrNICmp(zSpan, zDb, n)!=0 || zDb[n]!=0) ){
000138      return 0;
000139    }
000140    zSpan += n+1;
000141    for(n=0; ALWAYS(zSpan[n]) && zSpan[n]!='.'; n++){}
000142    if( zTab && (sqlite3StrNICmp(zSpan, zTab, n)!=0 || zTab[n]!=0) ){
000143      return 0;
000144    }
000145    zSpan += n+1;
000146    if( zCol && sqlite3StrICmp(zSpan, zCol)!=0 ){
000147      return 0;
000148    }
000149    return 1;
000150  }
000151  
000152  /*
000153  ** Given the name of a column of the form X.Y.Z or Y.Z or just Z, look up
000154  ** that name in the set of source tables in pSrcList and make the pExpr 
000155  ** expression node refer back to that source column.  The following changes
000156  ** are made to pExpr:
000157  **
000158  **    pExpr->iDb           Set the index in db->aDb[] of the database X
000159  **                         (even if X is implied).
000160  **    pExpr->iTable        Set to the cursor number for the table obtained
000161  **                         from pSrcList.
000162  **    pExpr->pTab          Points to the Table structure of X.Y (even if
000163  **                         X and/or Y are implied.)
000164  **    pExpr->iColumn       Set to the column number within the table.
000165  **    pExpr->op            Set to TK_COLUMN.
000166  **    pExpr->pLeft         Any expression this points to is deleted
000167  **    pExpr->pRight        Any expression this points to is deleted.
000168  **
000169  ** The zDb variable is the name of the database (the "X").  This value may be
000170  ** NULL meaning that name is of the form Y.Z or Z.  Any available database
000171  ** can be used.  The zTable variable is the name of the table (the "Y").  This
000172  ** value can be NULL if zDb is also NULL.  If zTable is NULL it
000173  ** means that the form of the name is Z and that columns from any table
000174  ** can be used.
000175  **
000176  ** If the name cannot be resolved unambiguously, leave an error message
000177  ** in pParse and return WRC_Abort.  Return WRC_Prune on success.
000178  */
000179  static int lookupName(
000180    Parse *pParse,       /* The parsing context */
000181    const char *zDb,     /* Name of the database containing table, or NULL */
000182    const char *zTab,    /* Name of table containing column, or NULL */
000183    const char *zCol,    /* Name of the column. */
000184    NameContext *pNC,    /* The name context used to resolve the name */
000185    Expr *pExpr          /* Make this EXPR node point to the selected column */
000186  ){
000187    int i, j;                         /* Loop counters */
000188    int cnt = 0;                      /* Number of matching column names */
000189    int cntTab = 0;                   /* Number of matching table names */
000190    int nSubquery = 0;                /* How many levels of subquery */
000191    sqlite3 *db = pParse->db;         /* The database connection */
000192    struct SrcList_item *pItem;       /* Use for looping over pSrcList items */
000193    struct SrcList_item *pMatch = 0;  /* The matching pSrcList item */
000194    NameContext *pTopNC = pNC;        /* First namecontext in the list */
000195    Schema *pSchema = 0;              /* Schema of the expression */
000196    int eNewExprOp = TK_COLUMN;       /* New value for pExpr->op on success */
000197    Table *pTab = 0;                  /* Table hold the row */
000198    Column *pCol;                     /* A column of pTab */
000199  
000200    assert( pNC );     /* the name context cannot be NULL. */
000201    assert( zCol );    /* The Z in X.Y.Z cannot be NULL */
000202    assert( !ExprHasProperty(pExpr, EP_TokenOnly|EP_Reduced) );
000203  
000204    /* Initialize the node to no-match */
000205    pExpr->iTable = -1;
000206    pExpr->pTab = 0;
000207    ExprSetVVAProperty(pExpr, EP_NoReduce);
000208  
000209    /* Translate the schema name in zDb into a pointer to the corresponding
000210    ** schema.  If not found, pSchema will remain NULL and nothing will match
000211    ** resulting in an appropriate error message toward the end of this routine
000212    */
000213    if( zDb ){
000214      testcase( pNC->ncFlags & NC_PartIdx );
000215      testcase( pNC->ncFlags & NC_IsCheck );
000216      if( (pNC->ncFlags & (NC_PartIdx|NC_IsCheck))!=0 ){
000217        /* Silently ignore database qualifiers inside CHECK constraints and
000218        ** partial indices.  Do not raise errors because that might break
000219        ** legacy and because it does not hurt anything to just ignore the
000220        ** database name. */
000221        zDb = 0;
000222      }else{
000223        for(i=0; i<db->nDb; i++){
000224          assert( db->aDb[i].zDbSName );
000225          if( sqlite3StrICmp(db->aDb[i].zDbSName,zDb)==0 ){
000226            pSchema = db->aDb[i].pSchema;
000227            break;
000228          }
000229        }
000230      }
000231    }
000232  
000233    /* Start at the inner-most context and move outward until a match is found */
000234    assert( pNC && cnt==0 );
000235    do{
000236      ExprList *pEList;
000237      SrcList *pSrcList = pNC->pSrcList;
000238  
000239      if( pSrcList ){
000240        for(i=0, pItem=pSrcList->a; i<pSrcList->nSrc; i++, pItem++){
000241          pTab = pItem->pTab;
000242          assert( pTab!=0 && pTab->zName!=0 );
000243          assert( pTab->nCol>0 );
000244          if( pItem->pSelect && (pItem->pSelect->selFlags & SF_NestedFrom)!=0 ){
000245            int hit = 0;
000246            pEList = pItem->pSelect->pEList;
000247            for(j=0; j<pEList->nExpr; j++){
000248              if( sqlite3MatchSpanName(pEList->a[j].zSpan, zCol, zTab, zDb) ){
000249                cnt++;
000250                cntTab = 2;
000251                pMatch = pItem;
000252                pExpr->iColumn = j;
000253                hit = 1;
000254              }
000255            }
000256            if( hit || zTab==0 ) continue;
000257          }
000258          if( zDb && pTab->pSchema!=pSchema ){
000259            continue;
000260          }
000261          if( zTab ){
000262            const char *zTabName = pItem->zAlias ? pItem->zAlias : pTab->zName;
000263            assert( zTabName!=0 );
000264            if( sqlite3StrICmp(zTabName, zTab)!=0 ){
000265              continue;
000266            }
000267          }
000268          if( 0==(cntTab++) ){
000269            pMatch = pItem;
000270          }
000271          for(j=0, pCol=pTab->aCol; j<pTab->nCol; j++, pCol++){
000272            if( sqlite3StrICmp(pCol->zName, zCol)==0 ){
000273              /* If there has been exactly one prior match and this match
000274              ** is for the right-hand table of a NATURAL JOIN or is in a 
000275              ** USING clause, then skip this match.
000276              */
000277              if( cnt==1 ){
000278                if( pItem->fg.jointype & JT_NATURAL ) continue;
000279                if( nameInUsingClause(pItem->pUsing, zCol) ) continue;
000280              }
000281              cnt++;
000282              pMatch = pItem;
000283              /* Substitute the rowid (column -1) for the INTEGER PRIMARY KEY */
000284              pExpr->iColumn = j==pTab->iPKey ? -1 : (i16)j;
000285              break;
000286            }
000287          }
000288        }
000289        if( pMatch ){
000290          pExpr->iTable = pMatch->iCursor;
000291          pExpr->pTab = pMatch->pTab;
000292          /* RIGHT JOIN not (yet) supported */
000293          assert( (pMatch->fg.jointype & JT_RIGHT)==0 );
000294          if( (pMatch->fg.jointype & JT_LEFT)!=0 ){
000295            ExprSetProperty(pExpr, EP_CanBeNull);
000296          }
000297          pSchema = pExpr->pTab->pSchema;
000298        }
000299      } /* if( pSrcList ) */
000300  
000301  #if !defined(SQLITE_OMIT_TRIGGER) || !defined(SQLITE_OMIT_UPSERT)
000302      /* If we have not already resolved the name, then maybe 
000303      ** it is a new.* or old.* trigger argument reference.  Or
000304      ** maybe it is an excluded.* from an upsert.
000305      */
000306      if( zDb==0 && zTab!=0 && cntTab==0 ){
000307        pTab = 0;
000308  #ifndef SQLITE_OMIT_TRIGGER
000309        if( pParse->pTriggerTab!=0 ){
000310          int op = pParse->eTriggerOp;
000311          assert( op==TK_DELETE || op==TK_UPDATE || op==TK_INSERT );
000312          if( op!=TK_DELETE && sqlite3StrICmp("new",zTab) == 0 ){
000313            pExpr->iTable = 1;
000314            pTab = pParse->pTriggerTab;
000315          }else if( op!=TK_INSERT && sqlite3StrICmp("old",zTab)==0 ){
000316            pExpr->iTable = 0;
000317            pTab = pParse->pTriggerTab;
000318          }
000319        }
000320  #endif /* SQLITE_OMIT_TRIGGER */
000321  #ifndef SQLITE_OMIT_UPSERT
000322        if( (pNC->ncFlags & NC_UUpsert)!=0 ){
000323          Upsert *pUpsert = pNC->uNC.pUpsert;
000324          if( pUpsert && sqlite3StrICmp("excluded",zTab)==0 ){
000325            pTab = pUpsert->pUpsertSrc->a[0].pTab;
000326            pExpr->iTable = 2;
000327          }
000328        }
000329  #endif /* SQLITE_OMIT_UPSERT */
000330  
000331        if( pTab ){ 
000332          int iCol;
000333          pSchema = pTab->pSchema;
000334          cntTab++;
000335          for(iCol=0, pCol=pTab->aCol; iCol<pTab->nCol; iCol++, pCol++){
000336            if( sqlite3StrICmp(pCol->zName, zCol)==0 ){
000337              if( iCol==pTab->iPKey ){
000338                iCol = -1;
000339              }
000340              break;
000341            }
000342          }
000343          if( iCol>=pTab->nCol && sqlite3IsRowid(zCol) && VisibleRowid(pTab) ){
000344            /* IMP: R-51414-32910 */
000345            iCol = -1;
000346          }
000347          if( iCol<pTab->nCol ){
000348            cnt++;
000349  #ifndef SQLITE_OMIT_UPSERT
000350            if( pExpr->iTable==2 ){
000351              testcase( iCol==(-1) );
000352              pExpr->iTable = pNC->uNC.pUpsert->regData + iCol;
000353              eNewExprOp = TK_REGISTER;
000354              ExprSetProperty(pExpr, EP_Alias);
000355            }else
000356  #endif /* SQLITE_OMIT_UPSERT */
000357            {
000358  #ifndef SQLITE_OMIT_TRIGGER
000359              if( iCol<0 ){
000360                pExpr->affinity = SQLITE_AFF_INTEGER;
000361              }else if( pExpr->iTable==0 ){
000362                testcase( iCol==31 );
000363                testcase( iCol==32 );
000364                pParse->oldmask |= (iCol>=32 ? 0xffffffff : (((u32)1)<<iCol));
000365              }else{
000366                testcase( iCol==31 );
000367                testcase( iCol==32 );
000368                pParse->newmask |= (iCol>=32 ? 0xffffffff : (((u32)1)<<iCol));
000369              }
000370              pExpr->pTab = pTab;
000371              pExpr->iColumn = (i16)iCol;
000372              eNewExprOp = TK_TRIGGER;
000373  #endif /* SQLITE_OMIT_TRIGGER */
000374            }
000375          }
000376        }
000377      }
000378  #endif /* !defined(SQLITE_OMIT_TRIGGER) || !defined(SQLITE_OMIT_UPSERT) */
000379  
000380      /*
000381      ** Perhaps the name is a reference to the ROWID
000382      */
000383      if( cnt==0
000384       && cntTab==1
000385       && pMatch
000386       && (pNC->ncFlags & NC_IdxExpr)==0
000387       && sqlite3IsRowid(zCol)
000388       && VisibleRowid(pMatch->pTab)
000389      ){
000390        cnt = 1;
000391        pExpr->iColumn = -1;
000392        pExpr->affinity = SQLITE_AFF_INTEGER;
000393      }
000394  
000395      /*
000396      ** If the input is of the form Z (not Y.Z or X.Y.Z) then the name Z
000397      ** might refer to an result-set alias.  This happens, for example, when
000398      ** we are resolving names in the WHERE clause of the following command:
000399      **
000400      **     SELECT a+b AS x FROM table WHERE x<10;
000401      **
000402      ** In cases like this, replace pExpr with a copy of the expression that
000403      ** forms the result set entry ("a+b" in the example) and return immediately.
000404      ** Note that the expression in the result set should have already been
000405      ** resolved by the time the WHERE clause is resolved.
000406      **
000407      ** The ability to use an output result-set column in the WHERE, GROUP BY,
000408      ** or HAVING clauses, or as part of a larger expression in the ORDER BY
000409      ** clause is not standard SQL.  This is a (goofy) SQLite extension, that
000410      ** is supported for backwards compatibility only. Hence, we issue a warning
000411      ** on sqlite3_log() whenever the capability is used.
000412      */
000413      if( (pNC->ncFlags & NC_UEList)!=0
000414       && cnt==0
000415       && zTab==0
000416      ){
000417        pEList = pNC->uNC.pEList;
000418        assert( pEList!=0 );
000419        for(j=0; j<pEList->nExpr; j++){
000420          char *zAs = pEList->a[j].zName;
000421          if( zAs!=0 && sqlite3StrICmp(zAs, zCol)==0 ){
000422            Expr *pOrig;
000423            assert( pExpr->pLeft==0 && pExpr->pRight==0 );
000424            assert( pExpr->x.pList==0 );
000425            assert( pExpr->x.pSelect==0 );
000426            pOrig = pEList->a[j].pExpr;
000427            if( (pNC->ncFlags&NC_AllowAgg)==0 && ExprHasProperty(pOrig, EP_Agg) ){
000428              sqlite3ErrorMsg(pParse, "misuse of aliased aggregate %s", zAs);
000429              return WRC_Abort;
000430            }
000431            if( sqlite3ExprVectorSize(pOrig)!=1 ){
000432              sqlite3ErrorMsg(pParse, "row value misused");
000433              return WRC_Abort;
000434            }
000435            resolveAlias(pParse, pEList, j, pExpr, "", nSubquery);
000436            cnt = 1;
000437            pMatch = 0;
000438            assert( zTab==0 && zDb==0 );
000439            goto lookupname_end;
000440          }
000441        } 
000442      }
000443  
000444      /* Advance to the next name context.  The loop will exit when either
000445      ** we have a match (cnt>0) or when we run out of name contexts.
000446      */
000447      if( cnt ) break;
000448      pNC = pNC->pNext;
000449      nSubquery++;
000450    }while( pNC );
000451  
000452  
000453    /*
000454    ** If X and Y are NULL (in other words if only the column name Z is
000455    ** supplied) and the value of Z is enclosed in double-quotes, then
000456    ** Z is a string literal if it doesn't match any column names.  In that
000457    ** case, we need to return right away and not make any changes to
000458    ** pExpr.
000459    **
000460    ** Because no reference was made to outer contexts, the pNC->nRef
000461    ** fields are not changed in any context.
000462    */
000463    if( cnt==0 && zTab==0 ){
000464      assert( pExpr->op==TK_ID );
000465      if( ExprHasProperty(pExpr,EP_DblQuoted) ){
000466        pExpr->op = TK_STRING;
000467        pExpr->pTab = 0;
000468        return WRC_Prune;
000469      }
000470      if( sqlite3ExprIdToTrueFalse(pExpr) ){
000471        return WRC_Prune;
000472      }
000473    }
000474  
000475    /*
000476    ** cnt==0 means there was not match.  cnt>1 means there were two or
000477    ** more matches.  Either way, we have an error.
000478    */
000479    if( cnt!=1 ){
000480      const char *zErr;
000481      zErr = cnt==0 ? "no such column" : "ambiguous column name";
000482      if( zDb ){
000483        sqlite3ErrorMsg(pParse, "%s: %s.%s.%s", zErr, zDb, zTab, zCol);
000484      }else if( zTab ){
000485        sqlite3ErrorMsg(pParse, "%s: %s.%s", zErr, zTab, zCol);
000486      }else{
000487        sqlite3ErrorMsg(pParse, "%s: %s", zErr, zCol);
000488      }
000489      pParse->checkSchema = 1;
000490      pTopNC->nErr++;
000491    }
000492  
000493    /* If a column from a table in pSrcList is referenced, then record
000494    ** this fact in the pSrcList.a[].colUsed bitmask.  Column 0 causes
000495    ** bit 0 to be set.  Column 1 sets bit 1.  And so forth.  If the
000496    ** column number is greater than the number of bits in the bitmask
000497    ** then set the high-order bit of the bitmask.
000498    */
000499    if( pExpr->iColumn>=0 && pMatch!=0 ){
000500      int n = pExpr->iColumn;
000501      testcase( n==BMS-1 );
000502      if( n>=BMS ){
000503        n = BMS-1;
000504      }
000505      assert( pMatch->iCursor==pExpr->iTable );
000506      pMatch->colUsed |= ((Bitmask)1)<<n;
000507    }
000508  
000509    /* Clean up and return
000510    */
000511    sqlite3ExprDelete(db, pExpr->pLeft);
000512    pExpr->pLeft = 0;
000513    sqlite3ExprDelete(db, pExpr->pRight);
000514    pExpr->pRight = 0;
000515    pExpr->op = eNewExprOp;
000516    ExprSetProperty(pExpr, EP_Leaf);
000517  lookupname_end:
000518    if( cnt==1 ){
000519      assert( pNC!=0 );
000520      if( !ExprHasProperty(pExpr, EP_Alias) ){
000521        sqlite3AuthRead(pParse, pExpr, pSchema, pNC->pSrcList);
000522      }
000523      /* Increment the nRef value on all name contexts from TopNC up to
000524      ** the point where the name matched. */
000525      for(;;){
000526        assert( pTopNC!=0 );
000527        pTopNC->nRef++;
000528        if( pTopNC==pNC ) break;
000529        pTopNC = pTopNC->pNext;
000530      }
000531      return WRC_Prune;
000532    } else {
000533      return WRC_Abort;
000534    }
000535  }
000536  
000537  /*
000538  ** Allocate and return a pointer to an expression to load the column iCol
000539  ** from datasource iSrc in SrcList pSrc.
000540  */
000541  Expr *sqlite3CreateColumnExpr(sqlite3 *db, SrcList *pSrc, int iSrc, int iCol){
000542    Expr *p = sqlite3ExprAlloc(db, TK_COLUMN, 0, 0);
000543    if( p ){
000544      struct SrcList_item *pItem = &pSrc->a[iSrc];
000545      p->pTab = pItem->pTab;
000546      p->iTable = pItem->iCursor;
000547      if( p->pTab->iPKey==iCol ){
000548        p->iColumn = -1;
000549      }else{
000550        p->iColumn = (ynVar)iCol;
000551        testcase( iCol==BMS );
000552        testcase( iCol==BMS-1 );
000553        pItem->colUsed |= ((Bitmask)1)<<(iCol>=BMS ? BMS-1 : iCol);
000554      }
000555    }
000556    return p;
000557  }
000558  
000559  /*
000560  ** Report an error that an expression is not valid for some set of
000561  ** pNC->ncFlags values determined by validMask.
000562  */
000563  static void notValid(
000564    Parse *pParse,       /* Leave error message here */
000565    NameContext *pNC,    /* The name context */
000566    const char *zMsg,    /* Type of error */
000567    int validMask        /* Set of contexts for which prohibited */
000568  ){
000569    assert( (validMask&~(NC_IsCheck|NC_PartIdx|NC_IdxExpr))==0 );
000570    if( (pNC->ncFlags & validMask)!=0 ){
000571      const char *zIn = "partial index WHERE clauses";
000572      if( pNC->ncFlags & NC_IdxExpr )      zIn = "index expressions";
000573  #ifndef SQLITE_OMIT_CHECK
000574      else if( pNC->ncFlags & NC_IsCheck ) zIn = "CHECK constraints";
000575  #endif
000576      sqlite3ErrorMsg(pParse, "%s prohibited in %s", zMsg, zIn);
000577    }
000578  }
000579  
000580  /*
000581  ** Expression p should encode a floating point value between 1.0 and 0.0.
000582  ** Return 1024 times this value.  Or return -1 if p is not a floating point
000583  ** value between 1.0 and 0.0.
000584  */
000585  static int exprProbability(Expr *p){
000586    double r = -1.0;
000587    if( p->op!=TK_FLOAT ) return -1;
000588    sqlite3AtoF(p->u.zToken, &r, sqlite3Strlen30(p->u.zToken), SQLITE_UTF8);
000589    assert( r>=0.0 );
000590    if( r>1.0 ) return -1;
000591    return (int)(r*134217728.0);
000592  }
000593  
000594  /*
000595  ** This routine is callback for sqlite3WalkExpr().
000596  **
000597  ** Resolve symbolic names into TK_COLUMN operators for the current
000598  ** node in the expression tree.  Return 0 to continue the search down
000599  ** the tree or 2 to abort the tree walk.
000600  **
000601  ** This routine also does error checking and name resolution for
000602  ** function names.  The operator for aggregate functions is changed
000603  ** to TK_AGG_FUNCTION.
000604  */
000605  static int resolveExprStep(Walker *pWalker, Expr *pExpr){
000606    NameContext *pNC;
000607    Parse *pParse;
000608  
000609    pNC = pWalker->u.pNC;
000610    assert( pNC!=0 );
000611    pParse = pNC->pParse;
000612    assert( pParse==pWalker->pParse );
000613  
000614  #ifndef NDEBUG
000615    if( pNC->pSrcList && pNC->pSrcList->nAlloc>0 ){
000616      SrcList *pSrcList = pNC->pSrcList;
000617      int i;
000618      for(i=0; i<pNC->pSrcList->nSrc; i++){
000619        assert( pSrcList->a[i].iCursor>=0 && pSrcList->a[i].iCursor<pParse->nTab);
000620      }
000621    }
000622  #endif
000623    switch( pExpr->op ){
000624  
000625  #if defined(SQLITE_ENABLE_UPDATE_DELETE_LIMIT) && !defined(SQLITE_OMIT_SUBQUERY)
000626      /* The special operator TK_ROW means use the rowid for the first
000627      ** column in the FROM clause.  This is used by the LIMIT and ORDER BY
000628      ** clause processing on UPDATE and DELETE statements.
000629      */
000630      case TK_ROW: {
000631        SrcList *pSrcList = pNC->pSrcList;
000632        struct SrcList_item *pItem;
000633        assert( pSrcList && pSrcList->nSrc==1 );
000634        pItem = pSrcList->a;
000635        assert( HasRowid(pItem->pTab) && pItem->pTab->pSelect==0 );
000636        pExpr->op = TK_COLUMN;
000637        pExpr->pTab = pItem->pTab;
000638        pExpr->iTable = pItem->iCursor;
000639        pExpr->iColumn = -1;
000640        pExpr->affinity = SQLITE_AFF_INTEGER;
000641        break;
000642      }
000643  #endif /* defined(SQLITE_ENABLE_UPDATE_DELETE_LIMIT)
000644            && !defined(SQLITE_OMIT_SUBQUERY) */
000645  
000646      /* A column name:                    ID
000647      ** Or table name and column name:    ID.ID
000648      ** Or a database, table and column:  ID.ID.ID
000649      **
000650      ** The TK_ID and TK_OUT cases are combined so that there will only
000651      ** be one call to lookupName().  Then the compiler will in-line 
000652      ** lookupName() for a size reduction and performance increase.
000653      */
000654      case TK_ID:
000655      case TK_DOT: {
000656        const char *zColumn;
000657        const char *zTable;
000658        const char *zDb;
000659        Expr *pRight;
000660  
000661        if( pExpr->op==TK_ID ){
000662          zDb = 0;
000663          zTable = 0;
000664          zColumn = pExpr->u.zToken;
000665        }else{
000666          notValid(pParse, pNC, "the \".\" operator", NC_IdxExpr);
000667          pRight = pExpr->pRight;
000668          if( pRight->op==TK_ID ){
000669            zDb = 0;
000670            zTable = pExpr->pLeft->u.zToken;
000671            zColumn = pRight->u.zToken;
000672          }else{
000673            assert( pRight->op==TK_DOT );
000674            zDb = pExpr->pLeft->u.zToken;
000675            zTable = pRight->pLeft->u.zToken;
000676            zColumn = pRight->pRight->u.zToken;
000677          }
000678        }
000679        return lookupName(pParse, zDb, zTable, zColumn, pNC, pExpr);
000680      }
000681  
000682      /* Resolve function names
000683      */
000684      case TK_FUNCTION: {
000685        ExprList *pList = pExpr->x.pList;    /* The argument list */
000686        int n = pList ? pList->nExpr : 0;    /* Number of arguments */
000687        int no_such_func = 0;       /* True if no such function exists */
000688        int wrong_num_args = 0;     /* True if wrong number of arguments */
000689        int is_agg = 0;             /* True if is an aggregate function */
000690        int nId;                    /* Number of characters in function name */
000691        const char *zId;            /* The function name. */
000692        FuncDef *pDef;              /* Information about the function */
000693        u8 enc = ENC(pParse->db);   /* The database encoding */
000694  
000695        assert( !ExprHasProperty(pExpr, EP_xIsSelect) );
000696        zId = pExpr->u.zToken;
000697        nId = sqlite3Strlen30(zId);
000698        pDef = sqlite3FindFunction(pParse->db, zId, n, enc, 0);
000699        if( pDef==0 ){
000700          pDef = sqlite3FindFunction(pParse->db, zId, -2, enc, 0);
000701          if( pDef==0 ){
000702            no_such_func = 1;
000703          }else{
000704            wrong_num_args = 1;
000705          }
000706        }else{
000707          is_agg = pDef->xFinalize!=0;
000708          if( pDef->funcFlags & SQLITE_FUNC_UNLIKELY ){
000709            ExprSetProperty(pExpr, EP_Unlikely|EP_Skip);
000710            if( n==2 ){
000711              pExpr->iTable = exprProbability(pList->a[1].pExpr);
000712              if( pExpr->iTable<0 ){
000713                sqlite3ErrorMsg(pParse,
000714                  "second argument to likelihood() must be a "
000715                  "constant between 0.0 and 1.0");
000716                pNC->nErr++;
000717              }
000718            }else{
000719              /* EVIDENCE-OF: R-61304-29449 The unlikely(X) function is
000720              ** equivalent to likelihood(X, 0.0625).
000721              ** EVIDENCE-OF: R-01283-11636 The unlikely(X) function is
000722              ** short-hand for likelihood(X,0.0625).
000723              ** EVIDENCE-OF: R-36850-34127 The likely(X) function is short-hand
000724              ** for likelihood(X,0.9375).
000725              ** EVIDENCE-OF: R-53436-40973 The likely(X) function is equivalent
000726              ** to likelihood(X,0.9375). */
000727              /* TUNING: unlikely() probability is 0.0625.  likely() is 0.9375 */
000728              pExpr->iTable = pDef->zName[0]=='u' ? 8388608 : 125829120;
000729            }             
000730          }
000731  #ifndef SQLITE_OMIT_AUTHORIZATION
000732          {
000733            int auth = sqlite3AuthCheck(pParse, SQLITE_FUNCTION, 0,pDef->zName,0);
000734            if( auth!=SQLITE_OK ){
000735              if( auth==SQLITE_DENY ){
000736                sqlite3ErrorMsg(pParse, "not authorized to use function: %s",
000737                                        pDef->zName);
000738                pNC->nErr++;
000739              }
000740              pExpr->op = TK_NULL;
000741              return WRC_Prune;
000742            }
000743          }
000744  #endif
000745          if( pDef->funcFlags & (SQLITE_FUNC_CONSTANT|SQLITE_FUNC_SLOCHNG) ){
000746            /* For the purposes of the EP_ConstFunc flag, date and time
000747            ** functions and other functions that change slowly are considered
000748            ** constant because they are constant for the duration of one query */
000749            ExprSetProperty(pExpr,EP_ConstFunc);
000750          }
000751          if( (pDef->funcFlags & SQLITE_FUNC_CONSTANT)==0 ){
000752            /* Date/time functions that use 'now', and other functions like
000753            ** sqlite_version() that might change over time cannot be used
000754            ** in an index. */
000755            notValid(pParse, pNC, "non-deterministic functions",
000756                     NC_IdxExpr|NC_PartIdx);
000757          }
000758        }
000759        if( is_agg && (pNC->ncFlags & NC_AllowAgg)==0 ){
000760          sqlite3ErrorMsg(pParse, "misuse of aggregate function %.*s()", nId,zId);
000761          pNC->nErr++;
000762          is_agg = 0;
000763        }else if( no_such_func && pParse->db->init.busy==0
000764  #ifdef SQLITE_ENABLE_UNKNOWN_SQL_FUNCTION
000765                  && pParse->explain==0
000766  #endif
000767        ){
000768          sqlite3ErrorMsg(pParse, "no such function: %.*s", nId, zId);
000769          pNC->nErr++;
000770        }else if( wrong_num_args ){
000771          sqlite3ErrorMsg(pParse,"wrong number of arguments to function %.*s()",
000772               nId, zId);
000773          pNC->nErr++;
000774        }
000775        if( is_agg ) pNC->ncFlags &= ~NC_AllowAgg;
000776        sqlite3WalkExprList(pWalker, pList);
000777        if( is_agg ){
000778          NameContext *pNC2 = pNC;
000779          pExpr->op = TK_AGG_FUNCTION;
000780          pExpr->op2 = 0;
000781          while( pNC2 && !sqlite3FunctionUsesThisSrc(pExpr, pNC2->pSrcList) ){
000782            pExpr->op2++;
000783            pNC2 = pNC2->pNext;
000784          }
000785          assert( pDef!=0 );
000786          if( pNC2 ){
000787            assert( SQLITE_FUNC_MINMAX==NC_MinMaxAgg );
000788            testcase( (pDef->funcFlags & SQLITE_FUNC_MINMAX)!=0 );
000789            pNC2->ncFlags |= NC_HasAgg | (pDef->funcFlags & SQLITE_FUNC_MINMAX);
000790  
000791          }
000792          pNC->ncFlags |= NC_AllowAgg;
000793        }
000794        /* FIX ME:  Compute pExpr->affinity based on the expected return
000795        ** type of the function 
000796        */
000797        return WRC_Prune;
000798      }
000799  #ifndef SQLITE_OMIT_SUBQUERY
000800      case TK_SELECT:
000801      case TK_EXISTS:  testcase( pExpr->op==TK_EXISTS );
000802  #endif
000803      case TK_IN: {
000804        testcase( pExpr->op==TK_IN );
000805        if( ExprHasProperty(pExpr, EP_xIsSelect) ){
000806          int nRef = pNC->nRef;
000807          notValid(pParse, pNC, "subqueries", NC_IsCheck|NC_PartIdx|NC_IdxExpr);
000808          sqlite3WalkSelect(pWalker, pExpr->x.pSelect);
000809          assert( pNC->nRef>=nRef );
000810          if( nRef!=pNC->nRef ){
000811            ExprSetProperty(pExpr, EP_VarSelect);
000812            pNC->ncFlags |= NC_VarSelect;
000813          }
000814        }
000815        break;
000816      }
000817      case TK_VARIABLE: {
000818        notValid(pParse, pNC, "parameters", NC_IsCheck|NC_PartIdx|NC_IdxExpr);
000819        break;
000820      }
000821      case TK_IS:
000822      case TK_ISNOT: {
000823        Expr *pRight;
000824        assert( !ExprHasProperty(pExpr, EP_Reduced) );
000825        /* Handle special cases of "x IS TRUE", "x IS FALSE", "x IS NOT TRUE",
000826        ** and "x IS NOT FALSE". */
000827        if( (pRight = pExpr->pRight)->op==TK_ID ){
000828          int rc = resolveExprStep(pWalker, pRight);
000829          if( rc==WRC_Abort ) return WRC_Abort;
000830          if( pRight->op==TK_TRUEFALSE ){
000831            pExpr->op2 = pExpr->op;
000832            pExpr->op = TK_TRUTH;
000833            return WRC_Continue;
000834          }
000835        }
000836        /* Fall thru */
000837      }
000838      case TK_BETWEEN:
000839      case TK_EQ:
000840      case TK_NE:
000841      case TK_LT:
000842      case TK_LE:
000843      case TK_GT:
000844      case TK_GE: {
000845        int nLeft, nRight;
000846        if( pParse->db->mallocFailed ) break;
000847        assert( pExpr->pLeft!=0 );
000848        nLeft = sqlite3ExprVectorSize(pExpr->pLeft);
000849        if( pExpr->op==TK_BETWEEN ){
000850          nRight = sqlite3ExprVectorSize(pExpr->x.pList->a[0].pExpr);
000851          if( nRight==nLeft ){
000852            nRight = sqlite3ExprVectorSize(pExpr->x.pList->a[1].pExpr);
000853          }
000854        }else{
000855          assert( pExpr->pRight!=0 );
000856          nRight = sqlite3ExprVectorSize(pExpr->pRight);
000857        }
000858        if( nLeft!=nRight ){
000859          testcase( pExpr->op==TK_EQ );
000860          testcase( pExpr->op==TK_NE );
000861          testcase( pExpr->op==TK_LT );
000862          testcase( pExpr->op==TK_LE );
000863          testcase( pExpr->op==TK_GT );
000864          testcase( pExpr->op==TK_GE );
000865          testcase( pExpr->op==TK_IS );
000866          testcase( pExpr->op==TK_ISNOT );
000867          testcase( pExpr->op==TK_BETWEEN );
000868          sqlite3ErrorMsg(pParse, "row value misused");
000869        }
000870        break; 
000871      }
000872    }
000873    return (pParse->nErr || pParse->db->mallocFailed) ? WRC_Abort : WRC_Continue;
000874  }
000875  
000876  /*
000877  ** pEList is a list of expressions which are really the result set of the
000878  ** a SELECT statement.  pE is a term in an ORDER BY or GROUP BY clause.
000879  ** This routine checks to see if pE is a simple identifier which corresponds
000880  ** to the AS-name of one of the terms of the expression list.  If it is,
000881  ** this routine return an integer between 1 and N where N is the number of
000882  ** elements in pEList, corresponding to the matching entry.  If there is
000883  ** no match, or if pE is not a simple identifier, then this routine
000884  ** return 0.
000885  **
000886  ** pEList has been resolved.  pE has not.
000887  */
000888  static int resolveAsName(
000889    Parse *pParse,     /* Parsing context for error messages */
000890    ExprList *pEList,  /* List of expressions to scan */
000891    Expr *pE           /* Expression we are trying to match */
000892  ){
000893    int i;             /* Loop counter */
000894  
000895    UNUSED_PARAMETER(pParse);
000896  
000897    if( pE->op==TK_ID ){
000898      char *zCol = pE->u.zToken;
000899      for(i=0; i<pEList->nExpr; i++){
000900        char *zAs = pEList->a[i].zName;
000901        if( zAs!=0 && sqlite3StrICmp(zAs, zCol)==0 ){
000902          return i+1;
000903        }
000904      }
000905    }
000906    return 0;
000907  }
000908  
000909  /*
000910  ** pE is a pointer to an expression which is a single term in the
000911  ** ORDER BY of a compound SELECT.  The expression has not been
000912  ** name resolved.
000913  **
000914  ** At the point this routine is called, we already know that the
000915  ** ORDER BY term is not an integer index into the result set.  That
000916  ** case is handled by the calling routine.
000917  **
000918  ** Attempt to match pE against result set columns in the left-most
000919  ** SELECT statement.  Return the index i of the matching column,
000920  ** as an indication to the caller that it should sort by the i-th column.
000921  ** The left-most column is 1.  In other words, the value returned is the
000922  ** same integer value that would be used in the SQL statement to indicate
000923  ** the column.
000924  **
000925  ** If there is no match, return 0.  Return -1 if an error occurs.
000926  */
000927  static int resolveOrderByTermToExprList(
000928    Parse *pParse,     /* Parsing context for error messages */
000929    Select *pSelect,   /* The SELECT statement with the ORDER BY clause */
000930    Expr *pE           /* The specific ORDER BY term */
000931  ){
000932    int i;             /* Loop counter */
000933    ExprList *pEList;  /* The columns of the result set */
000934    NameContext nc;    /* Name context for resolving pE */
000935    sqlite3 *db;       /* Database connection */
000936    int rc;            /* Return code from subprocedures */
000937    u8 savedSuppErr;   /* Saved value of db->suppressErr */
000938  
000939    assert( sqlite3ExprIsInteger(pE, &i)==0 );
000940    pEList = pSelect->pEList;
000941  
000942    /* Resolve all names in the ORDER BY term expression
000943    */
000944    memset(&nc, 0, sizeof(nc));
000945    nc.pParse = pParse;
000946    nc.pSrcList = pSelect->pSrc;
000947    nc.uNC.pEList = pEList;
000948    nc.ncFlags = NC_AllowAgg|NC_UEList;
000949    nc.nErr = 0;
000950    db = pParse->db;
000951    savedSuppErr = db->suppressErr;
000952    db->suppressErr = 1;
000953    rc = sqlite3ResolveExprNames(&nc, pE);
000954    db->suppressErr = savedSuppErr;
000955    if( rc ) return 0;
000956  
000957    /* Try to match the ORDER BY expression against an expression
000958    ** in the result set.  Return an 1-based index of the matching
000959    ** result-set entry.
000960    */
000961    for(i=0; i<pEList->nExpr; i++){
000962      if( sqlite3ExprCompare(0, pEList->a[i].pExpr, pE, -1)<2 ){
000963        return i+1;
000964      }
000965    }
000966  
000967    /* If no match, return 0. */
000968    return 0;
000969  }
000970  
000971  /*
000972  ** Generate an ORDER BY or GROUP BY term out-of-range error.
000973  */
000974  static void resolveOutOfRangeError(
000975    Parse *pParse,         /* The error context into which to write the error */
000976    const char *zType,     /* "ORDER" or "GROUP" */
000977    int i,                 /* The index (1-based) of the term out of range */
000978    int mx                 /* Largest permissible value of i */
000979  ){
000980    sqlite3ErrorMsg(pParse, 
000981      "%r %s BY term out of range - should be "
000982      "between 1 and %d", i, zType, mx);
000983  }
000984  
000985  /*
000986  ** Analyze the ORDER BY clause in a compound SELECT statement.   Modify
000987  ** each term of the ORDER BY clause is a constant integer between 1
000988  ** and N where N is the number of columns in the compound SELECT.
000989  **
000990  ** ORDER BY terms that are already an integer between 1 and N are
000991  ** unmodified.  ORDER BY terms that are integers outside the range of
000992  ** 1 through N generate an error.  ORDER BY terms that are expressions
000993  ** are matched against result set expressions of compound SELECT
000994  ** beginning with the left-most SELECT and working toward the right.
000995  ** At the first match, the ORDER BY expression is transformed into
000996  ** the integer column number.
000997  **
000998  ** Return the number of errors seen.
000999  */
001000  static int resolveCompoundOrderBy(
001001    Parse *pParse,        /* Parsing context.  Leave error messages here */
001002    Select *pSelect       /* The SELECT statement containing the ORDER BY */
001003  ){
001004    int i;
001005    ExprList *pOrderBy;
001006    ExprList *pEList;
001007    sqlite3 *db;
001008    int moreToDo = 1;
001009  
001010    pOrderBy = pSelect->pOrderBy;
001011    if( pOrderBy==0 ) return 0;
001012    db = pParse->db;
001013    if( pOrderBy->nExpr>db->aLimit[SQLITE_LIMIT_COLUMN] ){
001014      sqlite3ErrorMsg(pParse, "too many terms in ORDER BY clause");
001015      return 1;
001016    }
001017    for(i=0; i<pOrderBy->nExpr; i++){
001018      pOrderBy->a[i].done = 0;
001019    }
001020    pSelect->pNext = 0;
001021    while( pSelect->pPrior ){
001022      pSelect->pPrior->pNext = pSelect;
001023      pSelect = pSelect->pPrior;
001024    }
001025    while( pSelect && moreToDo ){
001026      struct ExprList_item *pItem;
001027      moreToDo = 0;
001028      pEList = pSelect->pEList;
001029      assert( pEList!=0 );
001030      for(i=0, pItem=pOrderBy->a; i<pOrderBy->nExpr; i++, pItem++){
001031        int iCol = -1;
001032        Expr *pE, *pDup;
001033        if( pItem->done ) continue;
001034        pE = sqlite3ExprSkipCollate(pItem->pExpr);
001035        if( sqlite3ExprIsInteger(pE, &iCol) ){
001036          if( iCol<=0 || iCol>pEList->nExpr ){
001037            resolveOutOfRangeError(pParse, "ORDER", i+1, pEList->nExpr);
001038            return 1;
001039          }
001040        }else{
001041          iCol = resolveAsName(pParse, pEList, pE);
001042          if( iCol==0 ){
001043            pDup = sqlite3ExprDup(db, pE, 0);
001044            if( !db->mallocFailed ){
001045              assert(pDup);
001046              iCol = resolveOrderByTermToExprList(pParse, pSelect, pDup);
001047            }
001048            sqlite3ExprDelete(db, pDup);
001049          }
001050        }
001051        if( iCol>0 ){
001052          /* Convert the ORDER BY term into an integer column number iCol,
001053          ** taking care to preserve the COLLATE clause if it exists */
001054          Expr *pNew = sqlite3Expr(db, TK_INTEGER, 0);
001055          if( pNew==0 ) return 1;
001056          pNew->flags |= EP_IntValue;
001057          pNew->u.iValue = iCol;
001058          if( pItem->pExpr==pE ){
001059            pItem->pExpr = pNew;
001060          }else{
001061            Expr *pParent = pItem->pExpr;
001062            assert( pParent->op==TK_COLLATE );
001063            while( pParent->pLeft->op==TK_COLLATE ) pParent = pParent->pLeft;
001064            assert( pParent->pLeft==pE );
001065            pParent->pLeft = pNew;
001066          }
001067          sqlite3ExprDelete(db, pE);
001068          pItem->u.x.iOrderByCol = (u16)iCol;
001069          pItem->done = 1;
001070        }else{
001071          moreToDo = 1;
001072        }
001073      }
001074      pSelect = pSelect->pNext;
001075    }
001076    for(i=0; i<pOrderBy->nExpr; i++){
001077      if( pOrderBy->a[i].done==0 ){
001078        sqlite3ErrorMsg(pParse, "%r ORDER BY term does not match any "
001079              "column in the result set", i+1);
001080        return 1;
001081      }
001082    }
001083    return 0;
001084  }
001085  
001086  /*
001087  ** Check every term in the ORDER BY or GROUP BY clause pOrderBy of
001088  ** the SELECT statement pSelect.  If any term is reference to a
001089  ** result set expression (as determined by the ExprList.a.u.x.iOrderByCol
001090  ** field) then convert that term into a copy of the corresponding result set
001091  ** column.
001092  **
001093  ** If any errors are detected, add an error message to pParse and
001094  ** return non-zero.  Return zero if no errors are seen.
001095  */
001096  int sqlite3ResolveOrderGroupBy(
001097    Parse *pParse,        /* Parsing context.  Leave error messages here */
001098    Select *pSelect,      /* The SELECT statement containing the clause */
001099    ExprList *pOrderBy,   /* The ORDER BY or GROUP BY clause to be processed */
001100    const char *zType     /* "ORDER" or "GROUP" */
001101  ){
001102    int i;
001103    sqlite3 *db = pParse->db;
001104    ExprList *pEList;
001105    struct ExprList_item *pItem;
001106  
001107    if( pOrderBy==0 || pParse->db->mallocFailed ) return 0;
001108    if( pOrderBy->nExpr>db->aLimit[SQLITE_LIMIT_COLUMN] ){
001109      sqlite3ErrorMsg(pParse, "too many terms in %s BY clause", zType);
001110      return 1;
001111    }
001112    pEList = pSelect->pEList;
001113    assert( pEList!=0 );  /* sqlite3SelectNew() guarantees this */
001114    for(i=0, pItem=pOrderBy->a; i<pOrderBy->nExpr; i++, pItem++){
001115      if( pItem->u.x.iOrderByCol ){
001116        if( pItem->u.x.iOrderByCol>pEList->nExpr ){
001117          resolveOutOfRangeError(pParse, zType, i+1, pEList->nExpr);
001118          return 1;
001119        }
001120        resolveAlias(pParse, pEList, pItem->u.x.iOrderByCol-1, pItem->pExpr,
001121                     zType,0);
001122      }
001123    }
001124    return 0;
001125  }
001126  
001127  /*
001128  ** pOrderBy is an ORDER BY or GROUP BY clause in SELECT statement pSelect.
001129  ** The Name context of the SELECT statement is pNC.  zType is either
001130  ** "ORDER" or "GROUP" depending on which type of clause pOrderBy is.
001131  **
001132  ** This routine resolves each term of the clause into an expression.
001133  ** If the order-by term is an integer I between 1 and N (where N is the
001134  ** number of columns in the result set of the SELECT) then the expression
001135  ** in the resolution is a copy of the I-th result-set expression.  If
001136  ** the order-by term is an identifier that corresponds to the AS-name of
001137  ** a result-set expression, then the term resolves to a copy of the
001138  ** result-set expression.  Otherwise, the expression is resolved in
001139  ** the usual way - using sqlite3ResolveExprNames().
001140  **
001141  ** This routine returns the number of errors.  If errors occur, then
001142  ** an appropriate error message might be left in pParse.  (OOM errors
001143  ** excepted.)
001144  */
001145  static int resolveOrderGroupBy(
001146    NameContext *pNC,     /* The name context of the SELECT statement */
001147    Select *pSelect,      /* The SELECT statement holding pOrderBy */
001148    ExprList *pOrderBy,   /* An ORDER BY or GROUP BY clause to resolve */
001149    const char *zType     /* Either "ORDER" or "GROUP", as appropriate */
001150  ){
001151    int i, j;                      /* Loop counters */
001152    int iCol;                      /* Column number */
001153    struct ExprList_item *pItem;   /* A term of the ORDER BY clause */
001154    Parse *pParse;                 /* Parsing context */
001155    int nResult;                   /* Number of terms in the result set */
001156  
001157    if( pOrderBy==0 ) return 0;
001158    nResult = pSelect->pEList->nExpr;
001159    pParse = pNC->pParse;
001160    for(i=0, pItem=pOrderBy->a; i<pOrderBy->nExpr; i++, pItem++){
001161      Expr *pE = pItem->pExpr;
001162      Expr *pE2 = sqlite3ExprSkipCollate(pE);
001163      if( zType[0]!='G' ){
001164        iCol = resolveAsName(pParse, pSelect->pEList, pE2);
001165        if( iCol>0 ){
001166          /* If an AS-name match is found, mark this ORDER BY column as being
001167          ** a copy of the iCol-th result-set column.  The subsequent call to
001168          ** sqlite3ResolveOrderGroupBy() will convert the expression to a
001169          ** copy of the iCol-th result-set expression. */
001170          pItem->u.x.iOrderByCol = (u16)iCol;
001171          continue;
001172        }
001173      }
001174      if( sqlite3ExprIsInteger(pE2, &iCol) ){
001175        /* The ORDER BY term is an integer constant.  Again, set the column
001176        ** number so that sqlite3ResolveOrderGroupBy() will convert the
001177        ** order-by term to a copy of the result-set expression */
001178        if( iCol<1 || iCol>0xffff ){
001179          resolveOutOfRangeError(pParse, zType, i+1, nResult);
001180          return 1;
001181        }
001182        pItem->u.x.iOrderByCol = (u16)iCol;
001183        continue;
001184      }
001185  
001186      /* Otherwise, treat the ORDER BY term as an ordinary expression */
001187      pItem->u.x.iOrderByCol = 0;
001188      if( sqlite3ResolveExprNames(pNC, pE) ){
001189        return 1;
001190      }
001191      for(j=0; j<pSelect->pEList->nExpr; j++){
001192        if( sqlite3ExprCompare(0, pE, pSelect->pEList->a[j].pExpr, -1)==0 ){
001193          pItem->u.x.iOrderByCol = j+1;
001194        }
001195      }
001196    }
001197    return sqlite3ResolveOrderGroupBy(pParse, pSelect, pOrderBy, zType);
001198  }
001199  
001200  /*
001201  ** Resolve names in the SELECT statement p and all of its descendants.
001202  */
001203  static int resolveSelectStep(Walker *pWalker, Select *p){
001204    NameContext *pOuterNC;  /* Context that contains this SELECT */
001205    NameContext sNC;        /* Name context of this SELECT */
001206    int isCompound;         /* True if p is a compound select */
001207    int nCompound;          /* Number of compound terms processed so far */
001208    Parse *pParse;          /* Parsing context */
001209    int i;                  /* Loop counter */
001210    ExprList *pGroupBy;     /* The GROUP BY clause */
001211    Select *pLeftmost;      /* Left-most of SELECT of a compound */
001212    sqlite3 *db;            /* Database connection */
001213    
001214  
001215    assert( p!=0 );
001216    if( p->selFlags & SF_Resolved ){
001217      return WRC_Prune;
001218    }
001219    pOuterNC = pWalker->u.pNC;
001220    pParse = pWalker->pParse;
001221    db = pParse->db;
001222  
001223    /* Normally sqlite3SelectExpand() will be called first and will have
001224    ** already expanded this SELECT.  However, if this is a subquery within
001225    ** an expression, sqlite3ResolveExprNames() will be called without a
001226    ** prior call to sqlite3SelectExpand().  When that happens, let
001227    ** sqlite3SelectPrep() do all of the processing for this SELECT.
001228    ** sqlite3SelectPrep() will invoke both sqlite3SelectExpand() and
001229    ** this routine in the correct order.
001230    */
001231    if( (p->selFlags & SF_Expanded)==0 ){
001232      sqlite3SelectPrep(pParse, p, pOuterNC);
001233      return (pParse->nErr || db->mallocFailed) ? WRC_Abort : WRC_Prune;
001234    }
001235  
001236    isCompound = p->pPrior!=0;
001237    nCompound = 0;
001238    pLeftmost = p;
001239    while( p ){
001240      assert( (p->selFlags & SF_Expanded)!=0 );
001241      assert( (p->selFlags & SF_Resolved)==0 );
001242      p->selFlags |= SF_Resolved;
001243  
001244      /* Resolve the expressions in the LIMIT and OFFSET clauses. These
001245      ** are not allowed to refer to any names, so pass an empty NameContext.
001246      */
001247      memset(&sNC, 0, sizeof(sNC));
001248      sNC.pParse = pParse;
001249      if( sqlite3ResolveExprNames(&sNC, p->pLimit) ){
001250        return WRC_Abort;
001251      }
001252  
001253      /* If the SF_Converted flags is set, then this Select object was
001254      ** was created by the convertCompoundSelectToSubquery() function.
001255      ** In this case the ORDER BY clause (p->pOrderBy) should be resolved
001256      ** as if it were part of the sub-query, not the parent. This block
001257      ** moves the pOrderBy down to the sub-query. It will be moved back
001258      ** after the names have been resolved.  */
001259      if( p->selFlags & SF_Converted ){
001260        Select *pSub = p->pSrc->a[0].pSelect;
001261        assert( p->pSrc->nSrc==1 && p->pOrderBy );
001262        assert( pSub->pPrior && pSub->pOrderBy==0 );
001263        pSub->pOrderBy = p->pOrderBy;
001264        p->pOrderBy = 0;
001265      }
001266    
001267      /* Recursively resolve names in all subqueries
001268      */
001269      for(i=0; i<p->pSrc->nSrc; i++){
001270        struct SrcList_item *pItem = &p->pSrc->a[i];
001271        if( pItem->pSelect ){
001272          NameContext *pNC;         /* Used to iterate name contexts */
001273          int nRef = 0;             /* Refcount for pOuterNC and outer contexts */
001274          const char *zSavedContext = pParse->zAuthContext;
001275  
001276          /* Count the total number of references to pOuterNC and all of its
001277          ** parent contexts. After resolving references to expressions in
001278          ** pItem->pSelect, check if this value has changed. If so, then
001279          ** SELECT statement pItem->pSelect must be correlated. Set the
001280          ** pItem->fg.isCorrelated flag if this is the case. */
001281          for(pNC=pOuterNC; pNC; pNC=pNC->pNext) nRef += pNC->nRef;
001282  
001283          if( pItem->zName ) pParse->zAuthContext = pItem->zName;
001284          sqlite3ResolveSelectNames(pParse, pItem->pSelect, pOuterNC);
001285          pParse->zAuthContext = zSavedContext;
001286          if( pParse->nErr || db->mallocFailed ) return WRC_Abort;
001287  
001288          for(pNC=pOuterNC; pNC; pNC=pNC->pNext) nRef -= pNC->nRef;
001289          assert( pItem->fg.isCorrelated==0 && nRef<=0 );
001290          pItem->fg.isCorrelated = (nRef!=0);
001291        }
001292      }
001293    
001294      /* Set up the local name-context to pass to sqlite3ResolveExprNames() to
001295      ** resolve the result-set expression list.
001296      */
001297      sNC.ncFlags = NC_AllowAgg;
001298      sNC.pSrcList = p->pSrc;
001299      sNC.pNext = pOuterNC;
001300    
001301      /* Resolve names in the result set. */
001302      if( sqlite3ResolveExprListNames(&sNC, p->pEList) ) return WRC_Abort;
001303    
001304      /* If there are no aggregate functions in the result-set, and no GROUP BY 
001305      ** expression, do not allow aggregates in any of the other expressions.
001306      */
001307      assert( (p->selFlags & SF_Aggregate)==0 );
001308      pGroupBy = p->pGroupBy;
001309      if( pGroupBy || (sNC.ncFlags & NC_HasAgg)!=0 ){
001310        assert( NC_MinMaxAgg==SF_MinMaxAgg );
001311        p->selFlags |= SF_Aggregate | (sNC.ncFlags&NC_MinMaxAgg);
001312      }else{
001313        sNC.ncFlags &= ~NC_AllowAgg;
001314      }
001315    
001316      /* If a HAVING clause is present, then there must be a GROUP BY clause.
001317      */
001318      if( p->pHaving && !pGroupBy ){
001319        sqlite3ErrorMsg(pParse, "a GROUP BY clause is required before HAVING");
001320        return WRC_Abort;
001321      }
001322    
001323      /* Add the output column list to the name-context before parsing the
001324      ** other expressions in the SELECT statement. This is so that
001325      ** expressions in the WHERE clause (etc.) can refer to expressions by
001326      ** aliases in the result set.
001327      **
001328      ** Minor point: If this is the case, then the expression will be
001329      ** re-evaluated for each reference to it.
001330      */
001331      assert( (sNC.ncFlags & (NC_UAggInfo|NC_UUpsert))==0 );
001332      sNC.uNC.pEList = p->pEList;
001333      sNC.ncFlags |= NC_UEList;
001334      if( sqlite3ResolveExprNames(&sNC, p->pHaving) ) return WRC_Abort;
001335      if( sqlite3ResolveExprNames(&sNC, p->pWhere) ) return WRC_Abort;
001336  
001337      /* Resolve names in table-valued-function arguments */
001338      for(i=0; i<p->pSrc->nSrc; i++){
001339        struct SrcList_item *pItem = &p->pSrc->a[i];
001340        if( pItem->fg.isTabFunc
001341         && sqlite3ResolveExprListNames(&sNC, pItem->u1.pFuncArg) 
001342        ){
001343          return WRC_Abort;
001344        }
001345      }
001346  
001347      /* The ORDER BY and GROUP BY clauses may not refer to terms in
001348      ** outer queries 
001349      */
001350      sNC.pNext = 0;
001351      sNC.ncFlags |= NC_AllowAgg;
001352  
001353      /* If this is a converted compound query, move the ORDER BY clause from 
001354      ** the sub-query back to the parent query. At this point each term
001355      ** within the ORDER BY clause has been transformed to an integer value.
001356      ** These integers will be replaced by copies of the corresponding result
001357      ** set expressions by the call to resolveOrderGroupBy() below.  */
001358      if( p->selFlags & SF_Converted ){
001359        Select *pSub = p->pSrc->a[0].pSelect;
001360        p->pOrderBy = pSub->pOrderBy;
001361        pSub->pOrderBy = 0;
001362      }
001363  
001364      /* Process the ORDER BY clause for singleton SELECT statements.
001365      ** The ORDER BY clause for compounds SELECT statements is handled
001366      ** below, after all of the result-sets for all of the elements of
001367      ** the compound have been resolved.
001368      **
001369      ** If there is an ORDER BY clause on a term of a compound-select other
001370      ** than the right-most term, then that is a syntax error.  But the error
001371      ** is not detected until much later, and so we need to go ahead and
001372      ** resolve those symbols on the incorrect ORDER BY for consistency.
001373      */
001374      if( isCompound<=nCompound  /* Defer right-most ORDER BY of a compound */
001375       && resolveOrderGroupBy(&sNC, p, p->pOrderBy, "ORDER")
001376      ){
001377        return WRC_Abort;
001378      }
001379      if( db->mallocFailed ){
001380        return WRC_Abort;
001381      }
001382    
001383      /* Resolve the GROUP BY clause.  At the same time, make sure 
001384      ** the GROUP BY clause does not contain aggregate functions.
001385      */
001386      if( pGroupBy ){
001387        struct ExprList_item *pItem;
001388      
001389        if( resolveOrderGroupBy(&sNC, p, pGroupBy, "GROUP") || db->mallocFailed ){
001390          return WRC_Abort;
001391        }
001392        for(i=0, pItem=pGroupBy->a; i<pGroupBy->nExpr; i++, pItem++){
001393          if( ExprHasProperty(pItem->pExpr, EP_Agg) ){
001394            sqlite3ErrorMsg(pParse, "aggregate functions are not allowed in "
001395                "the GROUP BY clause");
001396            return WRC_Abort;
001397          }
001398        }
001399      }
001400  
001401      /* If this is part of a compound SELECT, check that it has the right
001402      ** number of expressions in the select list. */
001403      if( p->pNext && p->pEList->nExpr!=p->pNext->pEList->nExpr ){
001404        sqlite3SelectWrongNumTermsError(pParse, p->pNext);
001405        return WRC_Abort;
001406      }
001407  
001408      /* Advance to the next term of the compound
001409      */
001410      p = p->pPrior;
001411      nCompound++;
001412    }
001413  
001414    /* Resolve the ORDER BY on a compound SELECT after all terms of
001415    ** the compound have been resolved.
001416    */
001417    if( isCompound && resolveCompoundOrderBy(pParse, pLeftmost) ){
001418      return WRC_Abort;
001419    }
001420  
001421    return WRC_Prune;
001422  }
001423  
001424  /*
001425  ** This routine walks an expression tree and resolves references to
001426  ** table columns and result-set columns.  At the same time, do error
001427  ** checking on function usage and set a flag if any aggregate functions
001428  ** are seen.
001429  **
001430  ** To resolve table columns references we look for nodes (or subtrees) of the 
001431  ** form X.Y.Z or Y.Z or just Z where
001432  **
001433  **      X:   The name of a database.  Ex:  "main" or "temp" or
001434  **           the symbolic name assigned to an ATTACH-ed database.
001435  **
001436  **      Y:   The name of a table in a FROM clause.  Or in a trigger
001437  **           one of the special names "old" or "new".
001438  **
001439  **      Z:   The name of a column in table Y.
001440  **
001441  ** The node at the root of the subtree is modified as follows:
001442  **
001443  **    Expr.op        Changed to TK_COLUMN
001444  **    Expr.pTab      Points to the Table object for X.Y
001445  **    Expr.iColumn   The column index in X.Y.  -1 for the rowid.
001446  **    Expr.iTable    The VDBE cursor number for X.Y
001447  **
001448  **
001449  ** To resolve result-set references, look for expression nodes of the
001450  ** form Z (with no X and Y prefix) where the Z matches the right-hand
001451  ** size of an AS clause in the result-set of a SELECT.  The Z expression
001452  ** is replaced by a copy of the left-hand side of the result-set expression.
001453  ** Table-name and function resolution occurs on the substituted expression
001454  ** tree.  For example, in:
001455  **
001456  **      SELECT a+b AS x, c+d AS y FROM t1 ORDER BY x;
001457  **
001458  ** The "x" term of the order by is replaced by "a+b" to render:
001459  **
001460  **      SELECT a+b AS x, c+d AS y FROM t1 ORDER BY a+b;
001461  **
001462  ** Function calls are checked to make sure that the function is 
001463  ** defined and that the correct number of arguments are specified.
001464  ** If the function is an aggregate function, then the NC_HasAgg flag is
001465  ** set and the opcode is changed from TK_FUNCTION to TK_AGG_FUNCTION.
001466  ** If an expression contains aggregate functions then the EP_Agg
001467  ** property on the expression is set.
001468  **
001469  ** An error message is left in pParse if anything is amiss.  The number
001470  ** if errors is returned.
001471  */
001472  int sqlite3ResolveExprNames( 
001473    NameContext *pNC,       /* Namespace to resolve expressions in. */
001474    Expr *pExpr             /* The expression to be analyzed. */
001475  ){
001476    u16 savedHasAgg;
001477    Walker w;
001478  
001479    if( pExpr==0 ) return SQLITE_OK;
001480    savedHasAgg = pNC->ncFlags & (NC_HasAgg|NC_MinMaxAgg);
001481    pNC->ncFlags &= ~(NC_HasAgg|NC_MinMaxAgg);
001482    w.pParse = pNC->pParse;
001483    w.xExprCallback = resolveExprStep;
001484    w.xSelectCallback = resolveSelectStep;
001485    w.xSelectCallback2 = 0;
001486    w.u.pNC = pNC;
001487  #if SQLITE_MAX_EXPR_DEPTH>0
001488    w.pParse->nHeight += pExpr->nHeight;
001489    if( sqlite3ExprCheckHeight(w.pParse, w.pParse->nHeight) ){
001490      return SQLITE_ERROR;
001491    }
001492  #endif
001493    sqlite3WalkExpr(&w, pExpr);
001494  #if SQLITE_MAX_EXPR_DEPTH>0
001495    w.pParse->nHeight -= pExpr->nHeight;
001496  #endif
001497    if( pNC->ncFlags & NC_HasAgg ){
001498      ExprSetProperty(pExpr, EP_Agg);
001499    }
001500    pNC->ncFlags |= savedHasAgg;
001501    return pNC->nErr>0 || w.pParse->nErr>0;
001502  }
001503  
001504  /*
001505  ** Resolve all names for all expression in an expression list.  This is
001506  ** just like sqlite3ResolveExprNames() except that it works for an expression
001507  ** list rather than a single expression.
001508  */
001509  int sqlite3ResolveExprListNames( 
001510    NameContext *pNC,       /* Namespace to resolve expressions in. */
001511    ExprList *pList         /* The expression list to be analyzed. */
001512  ){
001513    int i;
001514    if( pList ){
001515      for(i=0; i<pList->nExpr; i++){
001516        if( sqlite3ResolveExprNames(pNC, pList->a[i].pExpr) ) return WRC_Abort;
001517      }
001518    }
001519    return WRC_Continue;
001520  }
001521  
001522  /*
001523  ** Resolve all names in all expressions of a SELECT and in all
001524  ** decendents of the SELECT, including compounds off of p->pPrior,
001525  ** subqueries in expressions, and subqueries used as FROM clause
001526  ** terms.
001527  **
001528  ** See sqlite3ResolveExprNames() for a description of the kinds of
001529  ** transformations that occur.
001530  **
001531  ** All SELECT statements should have been expanded using
001532  ** sqlite3SelectExpand() prior to invoking this routine.
001533  */
001534  void sqlite3ResolveSelectNames(
001535    Parse *pParse,         /* The parser context */
001536    Select *p,             /* The SELECT statement being coded. */
001537    NameContext *pOuterNC  /* Name context for parent SELECT statement */
001538  ){
001539    Walker w;
001540  
001541    assert( p!=0 );
001542    w.xExprCallback = resolveExprStep;
001543    w.xSelectCallback = resolveSelectStep;
001544    w.xSelectCallback2 = 0;
001545    w.pParse = pParse;
001546    w.u.pNC = pOuterNC;
001547    sqlite3WalkSelect(&w, p);
001548  }
001549  
001550  /*
001551  ** Resolve names in expressions that can only reference a single table:
001552  **
001553  **    *   CHECK constraints
001554  **    *   WHERE clauses on partial indices
001555  **
001556  ** The Expr.iTable value for Expr.op==TK_COLUMN nodes of the expression
001557  ** is set to -1 and the Expr.iColumn value is set to the column number.
001558  **
001559  ** Any errors cause an error message to be set in pParse.
001560  */
001561  void sqlite3ResolveSelfReference(
001562    Parse *pParse,      /* Parsing context */
001563    Table *pTab,        /* The table being referenced */
001564    int type,           /* NC_IsCheck or NC_PartIdx or NC_IdxExpr */
001565    Expr *pExpr,        /* Expression to resolve.  May be NULL. */
001566    ExprList *pList     /* Expression list to resolve.  May be NULL. */
001567  ){
001568    SrcList sSrc;                   /* Fake SrcList for pParse->pNewTable */
001569    NameContext sNC;                /* Name context for pParse->pNewTable */
001570  
001571    assert( type==NC_IsCheck || type==NC_PartIdx || type==NC_IdxExpr );
001572    memset(&sNC, 0, sizeof(sNC));
001573    memset(&sSrc, 0, sizeof(sSrc));
001574    sSrc.nSrc = 1;
001575    sSrc.a[0].zName = pTab->zName;
001576    sSrc.a[0].pTab = pTab;
001577    sSrc.a[0].iCursor = -1;
001578    sNC.pParse = pParse;
001579    sNC.pSrcList = &sSrc;
001580    sNC.ncFlags = type;
001581    if( sqlite3ResolveExprNames(&sNC, pExpr) ) return;
001582    if( pList ) sqlite3ResolveExprListNames(&sNC, pList);
001583  }