/*

** 2008 August 18

**

** The author disclaims copyright to this source code.  In place of

** a legal notice, here is a blessing:

**

**    May you do good and not evil.

**    May you find forgiveness for yourself and forgive others.

**    May you share freely, never taking more than you give.

**

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

**

** This file contains routines used for walking the parser tree and

** resolve all identifiers by associating them with a particular

** table and column.

**

** $Id: resolve.c,v 1.5 2008/08/29 02:14:03 drh Exp $

*/

#include "sqliteInt.h"

#include <stdlib.h>

#include <string.h>

/*

** Turn the pExpr expression into an alias for the iCol-th column of the

** result set in pEList.

**

** If the result set column is a simple column reference, then this routine

** makes an exact copy.  But for any other kind of expression, this

** routine make a copy of the result set column as the argument to the

** TK_AS operator.  The TK_AS operator causes the expression to be

** evaluated just once and then reused for each alias.

**

** The reason for suppressing the TK_AS term when the expression is a simple

** column reference is so that the column reference will be recognized as

** usable by indices within the WHERE clause processing logic. 

**

** Hack:  The TK_AS operator is inhibited if zType[0]=='G'.  This means

** that in a GROUP BY clause, the expression is evaluated twice.  Hence:

**

**     SELECT random()%5 AS x, count(*) FROM tab GROUP BY x

**

** Is equivalent to:

**

**     SELECT random()%5 AS x, count(*) FROM tab GROUP BY random()%5

**

** The result of random()%5 in the GROUP BY clause is probably different

** from the result in the result-set.  We might fix this someday.  Or

** then again, we might not...

*/

static void resolveAlias(

  Parse *pParse,         /* Parsing context */

  ExprList *pEList,      /* A result set */

  int iCol,              /* A column in the result set.  0..pEList->nExpr-1 */

  Expr *pExpr,           /* Transform this into an alias to the result set */

  const char *zType      /* "GROUP" or "ORDER" or "" */

){

  Expr *pOrig;           /* The iCol-th column of the result set */

  Expr *pDup;            /* Copy of pOrig */

  sqlite3 *db;           /* The database connection */

  assert( iCol>=0 && iCol<pEList->nExpr );

  pOrig = pEList->a[iCol].pExpr;

  assert( pOrig!=0 );

  assert( pOrig->flags & EP_Resolved );

  db = pParse->db;

  pDup = sqlite3ExprDup(db, pOrig);

  if( pDup==0 ) return;

  if( pDup->op!=TK_COLUMN && zType[0]!='G' ){

    pDup = sqlite3PExpr(pParse, TK_AS, pDup, 0, 0);

    if( pDup==0 ) return;

    if( pEList->a[iCol].iAlias==0 ){

      pEList->a[iCol].iAlias = ++pParse->nAlias;

    }

    pDup->iTable = pEList->a[iCol].iAlias;

  }

  if( pExpr->flags & EP_ExpCollate ){

    pDup->pColl = pExpr->pColl;

    pDup->flags |= EP_ExpCollate;

  }

  if( pExpr->span.dyn ) sqlite3DbFree(db, (char*)pExpr->span.z);

  if( pExpr->token.dyn ) sqlite3DbFree(db, (char*)pExpr->token.z);

  memcpy(pExpr, pDup, sizeof(*pExpr));

  sqlite3DbFree(db, pDup);

}

/*

** Given the name of a column of the form X.Y.Z or Y.Z or just Z, look up

** that name in the set of source tables in pSrcList and make the pExpr 

** expression node refer back to that source column.  The following changes

** are made to pExpr:

**

**    pExpr->iDb           Set the index in db->aDb[] of the database X

**                         (even if X is implied).

**    pExpr->iTable        Set to the cursor number for the table obtained

**                         from pSrcList.

**    pExpr->pTab          Points to the Table structure of X.Y (even if

**                         X and/or Y are implied.)

**    pExpr->iColumn       Set to the column number within the table.

**    pExpr->op            Set to TK_COLUMN.

**    pExpr->pLeft         Any expression this points to is deleted

**    pExpr->pRight        Any expression this points to is deleted.

**

** The pDbToken is the name of the database (the "X").  This value may be

** NULL meaning that name is of the form Y.Z or Z.  Any available database

** can be used.  The pTableToken is the name of the table (the "Y").  This

** value can be NULL if pDbToken is also NULL.  If pTableToken is NULL it

** means that the form of the name is Z and that columns from any table

** can be used.

**

** If the name cannot be resolved unambiguously, leave an error message

** in pParse and return non-zero.  Return zero on success.

*/

static int lookupName(

  Parse *pParse,       /* The parsing context */

  Token *pDbToken,     /* Name of the database containing table, or NULL */

  Token *pTableToken,  /* Name of table containing column, or NULL */

  Token *pColumnToken, /* Name of the column. */

  NameContext *pNC,    /* The name context used to resolve the name */

  Expr *pExpr          /* Make this EXPR node point to the selected column */

){

  char *zDb = 0;       /* Name of the database.  The "X" in X.Y.Z */

  char *zTab = 0;      /* Name of the table.  The "Y" in X.Y.Z or Y.Z */

  char *zCol = 0;      /* Name of the column.  The "Z" */

  int i, j;            /* Loop counters */

  int cnt = 0;                      /* Number of matching column names */

  int cntTab = 0;                   /* Number of matching table names */

  sqlite3 *db = pParse->db;         /* The database connection */

  struct SrcList_item *pItem;       /* Use for looping over pSrcList items */

  struct SrcList_item *pMatch = 0;  /* The matching pSrcList item */

  NameContext *pTopNC = pNC;        /* First namecontext in the list */

  Schema *pSchema = 0;              /* Schema of the expression */

  assert( pColumnToken && pColumnToken->z ); /* The Z in X.Y.Z cannot be NULL */

  /* Dequote and zero-terminate the names */

  zDb = sqlite3NameFromToken(db, pDbToken);

  zTab = sqlite3NameFromToken(db, pTableToken);

  zCol = sqlite3NameFromToken(db, pColumnToken);

  if( db->mallocFailed ){

    goto lookupname_end;

  }

  /* Initialize the node to no-match */

  pExpr->iTable = -1;

  pExpr->pTab = 0;

  /* Start at the inner-most context and move outward until a match is found */

  while( pNC && cnt==0 ){

    ExprList *pEList;

    SrcList *pSrcList = pNC->pSrcList;

    if( pSrcList ){

      for(i=0, pItem=pSrcList->a; i<pSrcList->nSrc; i++, pItem++){

        Table *pTab;

        int iDb;

        Column *pCol;

        pTab = pItem->pTab;

        assert( pTab!=0 && pTab->zName!=0 );

        iDb = sqlite3SchemaToIndex(db, pTab->pSchema);

        assert( pTab->nCol>0 );

        if( zTab ){

          if( pItem->zAlias ){

            char *zTabName = pItem->zAlias;

            if( sqlite3StrICmp(zTabName, zTab)!=0 ) continue;

          }else{

            char *zTabName = pTab->zName;

            if( zTabName==0 || sqlite3StrICmp(zTabName, zTab)!=0 ) continue;

            if( zDb!=0 && sqlite3StrICmp(db->aDb[iDb].zName, zDb)!=0 ){

              continue;

            }

          }

        }

        if( 0==(cntTab++) ){

          pExpr->iTable = pItem->iCursor;

          pExpr->pTab = pTab;

          pSchema = pTab->pSchema;

          pMatch = pItem;

        }

        for(j=0, pCol=pTab->aCol; j<pTab->nCol; j++, pCol++){

          if( sqlite3StrICmp(pCol->zName, zCol)==0 ){

            IdList *pUsing;

            cnt++;

            pExpr->iTable = pItem->iCursor;

            pExpr->pTab = pTab;

            pMatch = pItem;

            pSchema = pTab->pSchema;

            /* Substitute the rowid (column -1) for the INTEGER PRIMARY KEY */

            pExpr->iColumn = j==pTab->iPKey ? -1 : j;

            if( i<pSrcList->nSrc-1 ){

              if( pItem[1].jointype & JT_NATURAL ){

                /* If this match occurred in the left table of a natural join,

                ** then skip the right table to avoid a duplicate match */

                pItem++;

                i++;

              }else if( (pUsing = pItem[1].pUsing)!=0 ){

                /* If this match occurs on a column that is in the USING clause

                ** of a join, skip the search of the right table of the join

                ** to avoid a duplicate match there. */

                int k;

                for(k=0; k<pUsing->nId; k++){

                  if( sqlite3StrICmp(pUsing->a[k].zName, zCol)==0 ){

                    pItem++;

                    i++;

                    break;

                  }

                }

              }

            }

            break;

          }

        }

      }

    }

#ifndef SQLITE_OMIT_TRIGGER

    /* If we have not already resolved the name, then maybe 

    ** it is a new.* or old.* trigger argument reference

    */

    if( zDb==0 && zTab!=0 && cnt==0 && pParse->trigStack!=0 ){

      TriggerStack *pTriggerStack = pParse->trigStack;

      Table *pTab = 0;

      u32 *piColMask;

      if( pTriggerStack->newIdx != -1 && sqlite3StrICmp("new", zTab) == 0 ){

        pExpr->iTable = pTriggerStack->newIdx;

        assert( pTriggerStack->pTab );

        pTab = pTriggerStack->pTab;

        piColMask = &(pTriggerStack->newColMask);

      }else if( pTriggerStack->oldIdx != -1 && sqlite3StrICmp("old", zTab)==0 ){

        pExpr->iTable = pTriggerStack->oldIdx;

        assert( pTriggerStack->pTab );

        pTab = pTriggerStack->pTab;

        piColMask = &(pTriggerStack->oldColMask);

      }

      if( pTab ){ 

        int iCol;

        Column *pCol = pTab->aCol;

        pSchema = pTab->pSchema;

        cntTab++;

        for(iCol=0; iCol < pTab->nCol; iCol++, pCol++) {

          if( sqlite3StrICmp(pCol->zName, zCol)==0 ){

            cnt++;

            pExpr->iColumn = iCol==pTab->iPKey ? -1 : iCol;

            pExpr->pTab = pTab;

            if( iCol>=0 ){

              testcase( iCol==31 );

              testcase( iCol==32 );

              *piColMask |= ((u32)1<<iCol) | (iCol>=32?0xffffffff:0);

            }

            break;

          }

        }

      }

    }

#endif /* !defined(SQLITE_OMIT_TRIGGER) */

    /*

    ** Perhaps the name is a reference to the ROWID

    */

    if( cnt==0 && cntTab==1 && sqlite3IsRowid(zCol) ){

      cnt = 1;

      pExpr->iColumn = -1;

      pExpr->affinity = SQLITE_AFF_INTEGER;

    }

    /*

    ** If the input is of the form Z (not Y.Z or X.Y.Z) then the name Z

    ** might refer to an result-set alias.  This happens, for example, when

    ** we are resolving names in the WHERE clause of the following command:

    **

    **     SELECT a+b AS x FROM table WHERE x<10;

    **

    ** In cases like this, replace pExpr with a copy of the expression that

    ** forms the result set entry ("a+b" in the example) and return immediately.

    ** Note that the expression in the result set should have already been

    ** resolved by the time the WHERE clause is resolved.

    */

    if( cnt==0 && (pEList = pNC->pEList)!=0 && zTab==0 ){

      for(j=0; j<pEList->nExpr; j++){

        char *zAs = pEList->a[j].zName;

        if( zAs!=0 && sqlite3StrICmp(zAs, zCol)==0 ){

          Expr *pOrig;

          assert( pExpr->pLeft==0 && pExpr->pRight==0 );

          assert( pExpr->pList==0 );

          assert( pExpr->pSelect==0 );

          pOrig = pEList->a[j].pExpr;

          if( !pNC->allowAgg && ExprHasProperty(pOrig, EP_Agg) ){

            sqlite3ErrorMsg(pParse, "misuse of aliased aggregate %s", zAs);

            sqlite3DbFree(db, zCol);

            return 2;

          }

          resolveAlias(pParse, pEList, j, pExpr, "");

          cnt = 1;

          pMatch = 0;

          assert( zTab==0 && zDb==0 );

          goto lookupname_end_2;

        }

      } 

    }

    /* Advance to the next name context.  The loop will exit when either

    ** we have a match (cnt>0) or when we run out of name contexts.

    */

    if( cnt==0 ){

      pNC = pNC->pNext;

    }

  }

  /*

  ** If X and Y are NULL (in other words if only the column name Z is

  ** supplied) and the value of Z is enclosed in double-quotes, then

  ** Z is a string literal if it doesn't match any column names.  In that

  ** case, we need to return right away and not make any changes to

  ** pExpr.

  **

  ** Because no reference was made to outer contexts, the pNC->nRef

  ** fields are not changed in any context.

  */

  if( cnt==0 && zTab==0 && pColumnToken->z[0]=='"' ){

    sqlite3DbFree(db, zCol);

    pExpr->op = TK_STRING;

    return 0;

  }

  /*

  ** cnt==0 means there was not match.  cnt>1 means there were two or

  ** more matches.  Either way, we have an error.

  */

  if( cnt!=1 ){

    const char *zErr;

    zErr = cnt==0 ? "no such column" : "ambiguous column name";

    if( zDb ){

      sqlite3ErrorMsg(pParse, "%s: %s.%s.%s", zErr, zDb, zTab, zCol);

    }else if( zTab ){

      sqlite3ErrorMsg(pParse, "%s: %s.%s", zErr, zTab, zCol);

    }else{

      sqlite3ErrorMsg(pParse, "%s: %s", zErr, zCol);

    }

    pTopNC->nErr++;

  }

  /* If a column from a table in pSrcList is referenced, then record

  ** this fact in the pSrcList.a[].colUsed bitmask.  Column 0 causes

  ** bit 0 to be set.  Column 1 sets bit 1.  And so forth.  If the

  ** column number is greater than the number of bits in the bitmask

  ** then set the high-order bit of the bitmask.

  */

  if( pExpr->iColumn>=0 && pMatch!=0 ){

    int n = pExpr->iColumn;

    testcase( n==sizeof(Bitmask)*8-1 );

    if( n>=sizeof(Bitmask)*8 ){

      n = sizeof(Bitmask)*8-1;

    }

    assert( pMatch->iCursor==pExpr->iTable );

    pMatch->colUsed |= ((Bitmask)1)<<n;

  }

lookupname_end:

  /* Clean up and return

  */

  sqlite3DbFree(db, zDb);

  sqlite3DbFree(db, zTab);

  sqlite3ExprDelete(db, pExpr->pLeft);

  pExpr->pLeft = 0;

  sqlite3ExprDelete(db, pExpr->pRight);

  pExpr->pRight = 0;

  pExpr->op = TK_COLUMN;

lookupname_end_2:

  sqlite3DbFree(db, zCol);

  if( cnt==1 ){

    assert( pNC!=0 );

    sqlite3AuthRead(pParse, pExpr, pSchema, pNC->pSrcList);

    /* Increment the nRef value on all name contexts from TopNC up to

    ** the point where the name matched. */

    for(;;){

      assert( pTopNC!=0 );

      pTopNC->nRef++;

      if( pTopNC==pNC ) break;

      pTopNC = pTopNC->pNext;

    }

    return 0;

  } else {

    return 1;

  }

}

/*

** This routine is callback for sqlite3WalkExpr().

**

** Resolve symbolic names into TK_COLUMN operators for the current

** node in the expression tree.  Return 0 to continue the search down

** the tree or 2 to abort the tree walk.

**

** This routine also does error checking and name resolution for

** function names.  The operator for aggregate functions is changed

** to TK_AGG_FUNCTION.

*/

static int resolveExprStep(Walker *pWalker, Expr *pExpr){

  NameContext *pNC;

  Parse *pParse;

  pNC = pWalker->u.pNC;

  assert( pNC!=0 );

  pParse = pNC->pParse;

  assert( pParse==pWalker->pParse );

  if( ExprHasAnyProperty(pExpr, EP_Resolved) ) return WRC_Prune;

  ExprSetProperty(pExpr, EP_Resolved);

#ifndef NDEBUG

  if( pNC->pSrcList && pNC->pSrcList->nAlloc>0 ){

    SrcList *pSrcList = pNC->pSrcList;

    int i;

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

      assert( pSrcList->a[i].iCursor>=0 && pSrcList->a[i].iCursor<pParse->nTab);

    }

  }

#endif

  switch( pExpr->op ){

    /* A lone identifier is the name of a column.

    */

    case TK_ID: {

      lookupName(pParse, 0, 0, &pExpr->token, pNC, pExpr);

      return WRC_Prune;

    }

    /* A table name and column name:     ID.ID

    ** Or a database, table and column:  ID.ID.ID

    */

    case TK_DOT: {

      Token *pColumn;

      Token *pTable;

      Token *pDb;

      Expr *pRight;

      /* if( pSrcList==0 ) break; */

      pRight = pExpr->pRight;

      if( pRight->op==TK_ID ){

        pDb = 0;

        pTable = &pExpr->pLeft->token;

        pColumn = &pRight->token;

      }else{

        assert( pRight->op==TK_DOT );

        pDb = &pExpr->pLeft->token;

        pTable = &pRight->pLeft->token;

        pColumn = &pRight->pRight->token;

      }

      lookupName(pParse, pDb, pTable, pColumn, pNC, pExpr);

      return WRC_Prune;

    }

    /* Resolve function names

    */

    case TK_CONST_FUNC:

    case TK_FUNCTION: {

      ExprList *pList = pExpr->pList;    /* The argument list */

      int n = pList ? pList->nExpr : 0;  /* Number of arguments */

      int no_such_func = 0;       /* True if no such function exists */

      int wrong_num_args = 0;     /* True if wrong number of arguments */

      int is_agg = 0;             /* True if is an aggregate function */

      int auth;                   /* Authorization to use the function */

      int nId;                    /* Number of characters in function name */

      const char *zId;            /* The function name. */

      FuncDef *pDef;              /* Information about the function */

      int enc = ENC(pParse->db);  /* The database encoding */

      zId = (char*)pExpr->token.z;

      nId = pExpr->token.n;

      pDef = sqlite3FindFunction(pParse->db, zId, nId, n, enc, 0);

      if( pDef==0 ){

        pDef = sqlite3FindFunction(pParse->db, zId, nId, -1, enc, 0);

        if( pDef==0 ){

          no_such_func = 1;

        }else{

          wrong_num_args = 1;

        }

      }else{

        is_agg = pDef->xFunc==0;

      }

#ifndef SQLITE_OMIT_AUTHORIZATION

      if( pDef ){

        auth = sqlite3AuthCheck(pParse, SQLITE_FUNCTION, 0, pDef->zName, 0);

        if( auth!=SQLITE_OK ){

          if( auth==SQLITE_DENY ){

            sqlite3ErrorMsg(pParse, "not authorized to use function: %s",

                                    pDef->zName);

            pNC->nErr++;

          }

          pExpr->op = TK_NULL;

          return WRC_Prune;

        }

      }

#endif

      if( is_agg && !pNC->allowAgg ){

        sqlite3ErrorMsg(pParse, "misuse of aggregate function %.*s()", nId,zId);

        pNC->nErr++;

        is_agg = 0;

      }else if( no_such_func ){

        sqlite3ErrorMsg(pParse, "no such function: %.*s", nId, zId);

        pNC->nErr++;

      }else if( wrong_num_args ){

        sqlite3ErrorMsg(pParse,"wrong number of arguments to function %.*s()",

             nId, zId);

        pNC->nErr++;

      }

      if( is_agg ){

        pExpr->op = TK_AGG_FUNCTION;

        pNC->hasAgg = 1;

      }

      if( is_agg ) pNC->allowAgg = 0;

      sqlite3WalkExprList(pWalker, pList);

      if( is_agg ) pNC->allowAgg = 1;

      /* FIX ME:  Compute pExpr->affinity based on the expected return

      ** type of the function 

      */

      return WRC_Prune;

    }

#ifndef SQLITE_OMIT_SUBQUERY

    case TK_SELECT:

    case TK_EXISTS:

#endif

    case TK_IN: {

      if( pExpr->pSelect ){

        int nRef = pNC->nRef;

#ifndef SQLITE_OMIT_CHECK

        if( pNC->isCheck ){

          sqlite3ErrorMsg(pParse,"subqueries prohibited in CHECK constraints");