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