/*

** 2001 September 15

**

** 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 C code routines that are called by the parser

** to handle SELECT statements in SQLite.

**

** $Id: select.c,v 1.320 2006/08/11 19:08:27 drh Exp $

*/

#include "sqliteInt.h"

/*

** Delete all the content of a Select structure but do not deallocate

** the select structure itself.

*/

static void clearSelect(Select *p){

  sqlite3ExprListDelete(p->pEList);

  sqlite3SrcListDelete(p->pSrc);

  sqlite3ExprDelete(p->pWhere);

  sqlite3ExprListDelete(p->pGroupBy);

  sqlite3ExprDelete(p->pHaving);

  sqlite3ExprListDelete(p->pOrderBy);

  sqlite3SelectDelete(p->pPrior);

  sqlite3ExprDelete(p->pLimit);

  sqlite3ExprDelete(p->pOffset);

}

/*

** Allocate a new Select structure and return a pointer to that

** structure.

*/

Select *sqlite3SelectNew(

  ExprList *pEList,     /* which columns to include in the result */

  SrcList *pSrc,        /* the FROM clause -- which tables to scan */

  Expr *pWhere,         /* the WHERE clause */

  ExprList *pGroupBy,   /* the GROUP BY clause */

  Expr *pHaving,        /* the HAVING clause */

  ExprList *pOrderBy,   /* the ORDER BY clause */

  int isDistinct,       /* true if the DISTINCT keyword is present */

  Expr *pLimit,         /* LIMIT value.  NULL means not used */

  Expr *pOffset         /* OFFSET value.  NULL means no offset */

){

  Select *pNew;

  Select standin;

  pNew = sqliteMalloc( sizeof(*pNew) );

  assert( !pOffset || pLimit );   /* Can't have OFFSET without LIMIT. */

  if( pNew==0 ){

    pNew = &standin;

    memset(pNew, 0, sizeof(*pNew));

  }

  if( pEList==0 ){

    pEList = sqlite3ExprListAppend(0, sqlite3Expr(TK_ALL,0,0,0), 0);

  }

  pNew->pEList = pEList;

  pNew->pSrc = pSrc;

  pNew->pWhere = pWhere;

  pNew->pGroupBy = pGroupBy;

  pNew->pHaving = pHaving;

  pNew->pOrderBy = pOrderBy;

  pNew->isDistinct = isDistinct;

  pNew->op = TK_SELECT;

  pNew->pLimit = pLimit;

  pNew->pOffset = pOffset;

  pNew->iLimit = -1;

  pNew->iOffset = -1;

  pNew->addrOpenEphm[0] = -1;

  pNew->addrOpenEphm[1] = -1;

  pNew->addrOpenEphm[2] = -1;

  if( pNew==&standin) {

    clearSelect(pNew);

    pNew = 0;

  }

  return pNew;

}

/*

** Delete the given Select structure and all of its substructures.

*/

void sqlite3SelectDelete(Select *p){

  if( p ){

    clearSelect(p);

    sqliteFree(p);

  }

}

/*

** Given 1 to 3 identifiers preceeding the JOIN keyword, determine the

** type of join.  Return an integer constant that expresses that type

** in terms of the following bit values:

**

**     JT_INNER

**     JT_CROSS

**     JT_OUTER

**     JT_NATURAL

**     JT_LEFT

**     JT_RIGHT

**

** A full outer join is the combination of JT_LEFT and JT_RIGHT.

**

** If an illegal or unsupported join type is seen, then still return

** a join type, but put an error in the pParse structure.

*/

int sqlite3JoinType(Parse *pParse, Token *pA, Token *pB, Token *pC){

  int jointype = 0;

  Token *apAll[3];

  Token *p;

  static const struct {

    const char zKeyword[8];

    u8 nChar;

    u8 code;

  } keywords[] = {

    { "natural", 7, JT_NATURAL },

    { "left",    4, JT_LEFT|JT_OUTER },

    { "right",   5, JT_RIGHT|JT_OUTER },

    { "full",    4, JT_LEFT|JT_RIGHT|JT_OUTER },

    { "outer",   5, JT_OUTER },

    { "inner",   5, JT_INNER },

    { "cross",   5, JT_INNER|JT_CROSS },

  };

  int i, j;

  apAll[0] = pA;

  apAll[1] = pB;

  apAll[2] = pC;

  for(i=0; i<3 && apAll[i]; i++){

    p = apAll[i];

    for(j=0; j<sizeof(keywords)/sizeof(keywords[0]); j++){

      if( p->n==keywords[j].nChar 

          && sqlite3StrNICmp((char*)p->z, keywords[j].zKeyword, p->n)==0 ){

        jointype |= keywords[j].code;

        break;

      }

    }

    if( j>=sizeof(keywords)/sizeof(keywords[0]) ){

      jointype |= JT_ERROR;

      break;

    }

  }

  if(

     (jointype & (JT_INNER|JT_OUTER))==(JT_INNER|JT_OUTER) ||

     (jointype & JT_ERROR)!=0

  ){

    const char *zSp1 = " ";

    const char *zSp2 = " ";

    if( pB==0 ){ zSp1++; }

    if( pC==0 ){ zSp2++; }

    sqlite3ErrorMsg(pParse, "unknown or unsupported join type: "

       "%T%s%T%s%T", pA, zSp1, pB, zSp2, pC);

    jointype = JT_INNER;

  }else if( jointype & JT_RIGHT ){

    sqlite3ErrorMsg(pParse, 

      "RIGHT and FULL OUTER JOINs are not currently supported");

    jointype = JT_INNER;

  }

  return jointype;

}

/*

** Return the index of a column in a table.  Return -1 if the column

** is not contained in the table.

*/

static int columnIndex(Table *pTab, const char *zCol){

  int i;

  for(i=0; i<pTab->nCol; i++){

    if( sqlite3StrICmp(pTab->aCol[i].zName, zCol)==0 ) return i;

  }

  return -1;

}

/*

** Set the value of a token to a '\000'-terminated string.

*/

static void setToken(Token *p, const char *z){

  p->z = (u8*)z;

  p->n = z ? strlen(z) : 0;

  p->dyn = 0;

}

/*

** Create an expression node for an identifier with the name of zName

*/

Expr *sqlite3CreateIdExpr(const char *zName){

  Token dummy;

  setToken(&dummy, zName);

  return sqlite3Expr(TK_ID, 0, 0, &dummy);

}

/*

** Add a term to the WHERE expression in *ppExpr that requires the

** zCol column to be equal in the two tables pTab1 and pTab2.

*/

static void addWhereTerm(

  const char *zCol,        /* Name of the column */

  const Table *pTab1,      /* First table */

  const char *zAlias1,     /* Alias for first table.  May be NULL */

  const Table *pTab2,      /* Second table */

  const char *zAlias2,     /* Alias for second table.  May be NULL */

  int iRightJoinTable,     /* VDBE cursor for the right table */

  Expr **ppExpr            /* Add the equality term to this expression */

){

  Expr *pE1a, *pE1b, *pE1c;

  Expr *pE2a, *pE2b, *pE2c;

  Expr *pE;

  pE1a = sqlite3CreateIdExpr(zCol);

  pE2a = sqlite3CreateIdExpr(zCol);

  if( zAlias1==0 ){

    zAlias1 = pTab1->zName;

  }

  pE1b = sqlite3CreateIdExpr(zAlias1);

  if( zAlias2==0 ){

    zAlias2 = pTab2->zName;

  }

  pE2b = sqlite3CreateIdExpr(zAlias2);

  pE1c = sqlite3ExprOrFree(TK_DOT, pE1b, pE1a, 0);

  pE2c = sqlite3ExprOrFree(TK_DOT, pE2b, pE2a, 0);

  pE = sqlite3ExprOrFree(TK_EQ, pE1c, pE2c, 0);

  if( pE ){

    ExprSetProperty(pE, EP_FromJoin);

    pE->iRightJoinTable = iRightJoinTable;

  }

  pE = sqlite3ExprAnd(*ppExpr, pE);

  if( pE ){

    *ppExpr = pE;

  }

}

/*

** Set the EP_FromJoin property on all terms of the given expression.

** And set the Expr.iRightJoinTable to iTable for every term in the

** expression.

**

** The EP_FromJoin property is used on terms of an expression to tell

** the LEFT OUTER JOIN processing logic that this term is part of the

** join restriction specified in the ON or USING clause and not a part

** of the more general WHERE clause.  These terms are moved over to the

** WHERE clause during join processing but we need to remember that they

** originated in the ON or USING clause.

**

** The Expr.iRightJoinTable tells the WHERE clause processing that the

** expression depends on table iRightJoinTable even if that table is not

** explicitly mentioned in the expression.  That information is needed

** for cases like this:

**

**    SELECT * FROM t1 LEFT JOIN t2 ON t1.a=t2.b AND t1.x=5

**

** The where clause needs to defer the handling of the t1.x=5

** term until after the t2 loop of the join.  In that way, a

** NULL t2 row will be inserted whenever t1.x!=5.  If we do not

** defer the handling of t1.x=5, it will be processed immediately

** after the t1 loop and rows with t1.x!=5 will never appear in

** the output, which is incorrect.

*/

static void setJoinExpr(Expr *p, int iTable){

  while( p ){

    ExprSetProperty(p, EP_FromJoin);

    p->iRightJoinTable = iTable;

    setJoinExpr(p->pLeft, iTable);

    p = p->pRight;

  } 

}

/*

** This routine processes the join information for a SELECT statement.

** ON and USING clauses are converted into extra terms of the WHERE clause.

** NATURAL joins also create extra WHERE clause terms.

**

** The terms of a FROM clause are contained in the Select.pSrc structure.

** The left most table is the first entry in Select.pSrc.  The right-most

** table is the last entry.  The join operator is held in the entry to

** the left.  Thus entry 0 contains the join operator for the join between

** entries 0 and 1.  Any ON or USING clauses associated with the join are

** also attached to the left entry.

**

** This routine returns the number of errors encountered.

*/

static int sqliteProcessJoin(Parse *pParse, Select *p){

  SrcList *pSrc;                  /* All tables in the FROM clause */

  int i, j;                       /* Loop counters */

  struct SrcList_item *pLeft;     /* Left table being joined */

  struct SrcList_item *pRight;    /* Right table being joined */

  pSrc = p->pSrc;

  pLeft = &pSrc->a[0];

  pRight = &pLeft[1];

  for(i=0; i<pSrc->nSrc-1; i++, pRight++, pLeft++){

    Table *pLeftTab = pLeft->pTab;

    Table *pRightTab = pRight->pTab;

    if( pLeftTab==0 || pRightTab==0 ) continue;

    /* When the NATURAL keyword is present, add WHERE clause terms for

    ** every column that the two tables have in common.

    */

    if( pLeft->jointype & JT_NATURAL ){

      if( pLeft->pOn || pLeft->pUsing ){

        sqlite3ErrorMsg(pParse, "a NATURAL join may not have "

           "an ON or USING clause", 0);

        return 1;

      }

      for(j=0; j<pLeftTab->nCol; j++){

        char *zName = pLeftTab->aCol[j].zName;

        if( columnIndex(pRightTab, zName)>=0 ){

          addWhereTerm(zName, pLeftTab, pLeft->zAlias, 

                              pRightTab, pRight->zAlias,

                              pRight->iCursor, &p->pWhere);

        }

      }

    }

    /* Disallow both ON and USING clauses in the same join

    */

    if( pLeft->pOn && pLeft->pUsing ){

      sqlite3ErrorMsg(pParse, "cannot have both ON and USING "

        "clauses in the same join");

      return 1;

    }

    /* Add the ON clause to the end of the WHERE clause, connected by

    ** an AND operator.

    */

    if( pLeft->pOn ){

      setJoinExpr(pLeft->pOn, pRight->iCursor);

      p->pWhere = sqlite3ExprAnd(p->pWhere, pLeft->pOn);

      pLeft->pOn = 0;

    }

    /* Create extra terms on the WHERE clause for each column named

    ** in the USING clause.  Example: If the two tables to be joined are 

    ** A and B and the USING clause names X, Y, and Z, then add this

    ** to the WHERE clause:    A.X=B.X AND A.Y=B.Y AND A.Z=B.Z

    ** Report an error if any column mentioned in the USING clause is

    ** not contained in both tables to be joined.

    */

    if( pLeft->pUsing ){

      IdList *pList = pLeft->pUsing;

      for(j=0; j<pList->nId; j++){

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

        if( columnIndex(pLeftTab, zName)<0 || columnIndex(pRightTab, zName)<0 ){

          sqlite3ErrorMsg(pParse, "cannot join using column %s - column "

            "not present in both tables", zName);

          return 1;

        }

        addWhereTerm(zName, pLeftTab, pLeft->zAlias, 

                            pRightTab, pRight->zAlias,

                            pRight->iCursor, &p->pWhere);

      }

    }

  }

  return 0;

}

/*

** Insert code into "v" that will push the record on the top of the

** stack into the sorter.

*/

static void pushOntoSorter(

  Parse *pParse,         /* Parser context */

  ExprList *pOrderBy,    /* The ORDER BY clause */

  Select *pSelect        /* The whole SELECT statement */

){

  Vdbe *v = pParse->pVdbe;

  sqlite3ExprCodeExprList(pParse, pOrderBy);

  sqlite3VdbeAddOp(v, OP_Sequence, pOrderBy->iECursor, 0);

  sqlite3VdbeAddOp(v, OP_Pull, pOrderBy->nExpr + 1, 0);

  sqlite3VdbeAddOp(v, OP_MakeRecord, pOrderBy->nExpr + 2, 0);

  sqlite3VdbeAddOp(v, OP_IdxInsert, pOrderBy->iECursor, 0);

  if( pSelect->iLimit>=0 ){

    int addr1, addr2;

    addr1 = sqlite3VdbeAddOp(v, OP_IfMemZero, pSelect->iLimit+1, 0);

    sqlite3VdbeAddOp(v, OP_MemIncr, -1, pSelect->iLimit+1);

    addr2 = sqlite3VdbeAddOp(v, OP_Goto, 0, 0);

    sqlite3VdbeJumpHere(v, addr1);

    sqlite3VdbeAddOp(v, OP_Last, pOrderBy->iECursor, 0);

    sqlite3VdbeAddOp(v, OP_Delete, pOrderBy->iECursor, 0);

    sqlite3VdbeJumpHere(v, addr2);

    pSelect->iLimit = -1;

  }

}

/*

** Add code to implement the OFFSET

*/

static void codeOffset(

  Vdbe *v,          /* Generate code into this VM */

  Select *p,        /* The SELECT statement being coded */

  int iContinue,    /* Jump here to skip the current record */

  int nPop          /* Number of times to pop stack when jumping */

){

  if( p->iOffset>=0 && iContinue!=0 ){

    int addr;

    sqlite3VdbeAddOp(v, OP_MemIncr, -1, p->iOffset);

    addr = sqlite3VdbeAddOp(v, OP_IfMemNeg, p->iOffset, 0);

    if( nPop>0 ){

      sqlite3VdbeAddOp(v, OP_Pop, nPop, 0);

    }

    sqlite3VdbeAddOp(v, OP_Goto, 0, iContinue);

    VdbeComment((v, "# skip OFFSET records"));

    sqlite3VdbeJumpHere(v, addr);

  }

}

/*

** Add code that will check to make sure the top N elements of the

** stack are distinct.  iTab is a sorting index that holds previously

** seen combinations of the N values.  A new entry is made in iTab

** if the current N values are new.

**

** A jump to addrRepeat is made and the N+1 values are popped from the

** stack if the top N elements are not distinct.

*/

static void codeDistinct(

  Vdbe *v,           /* Generate code into this VM */

  int iTab,          /* A sorting index used to test for distinctness */

  int addrRepeat,    /* Jump to here if not distinct */

  int N              /* The top N elements of the stack must be distinct */

){

  sqlite3VdbeAddOp(v, OP_MakeRecord, -N, 0);

  sqlite3VdbeAddOp(v, OP_Distinct, iTab, sqlite3VdbeCurrentAddr(v)+3);

  sqlite3VdbeAddOp(v, OP_Pop, N+1, 0);

  sqlite3VdbeAddOp(v, OP_Goto, 0, addrRepeat);

  VdbeComment((v, "# skip indistinct records"));

  sqlite3VdbeAddOp(v, OP_IdxInsert, iTab, 0);

}

/*

** This routine generates the code for the inside of the inner loop

** of a SELECT.

**

** If srcTab and nColumn are both zero, then the pEList expressions

** are evaluated in order to get the data for this row.  If nColumn>0

** then data is pulled from srcTab and pEList is used only to get the

** datatypes for each column.

*/

static int selectInnerLoop(

  Parse *pParse,          /* The parser context */

  Select *p,              /* The complete select statement being coded */

  ExprList *pEList,       /* List of values being extracted */

  int srcTab,             /* Pull data from this table */

  int nColumn,            /* Number of columns in the source table */

  ExprList *pOrderBy,     /* If not NULL, sort results using this key */

  int distinct,           /* If >=0, make sure results are distinct */

  int eDest,              /* How to dispose of the results */

  int iParm,              /* An argument to the disposal method */

  int iContinue,          /* Jump here to continue with next row */

  int iBreak,             /* Jump here to break out of the inner loop */

  char *aff               /* affinity string if eDest is SRT_Union */

){

  Vdbe *v = pParse->pVdbe;

  int i;

  int hasDistinct;        /* True if the DISTINCT keyword is present */

  if( v==0 ) return 0;

  assert( pEList!=0 );

  /* If there was a LIMIT clause on the SELECT statement, then do the check

  ** to see if this row should be output.

  */

  hasDistinct = distinct>=0 && pEList->nExpr>0;

  if( pOrderBy==0 && !hasDistinct ){

    codeOffset(v, p, iContinue, 0);

  }

  /* Pull the requested columns.

  */

  if( nColumn>0 ){

    for(i=0; i<nColumn; i++){

      sqlite3VdbeAddOp(v, OP_Column, srcTab, i);

    }

  }else{

    nColumn = pEList->nExpr;

    sqlite3ExprCodeExprList(pParse, pEList);

  }

  /* If the DISTINCT keyword was present on the SELECT statement

  ** and this row has been seen before, then do not make this row

  ** part of the result.

  */

  if( hasDistinct ){

    assert( pEList!=0 );

    assert( pEList->nExpr==nColumn );

    codeDistinct(v, distinct, iContinue, nColumn);

    if( pOrderBy==0 ){

      codeOffset(v, p, iContinue, nColumn);

    }

  }

  switch( eDest ){

    /* In this mode, write each query result to the key of the temporary

    ** table iParm.

    */

#ifndef SQLITE_OMIT_COMPOUND_SELECT

    case SRT_Union: {

      sqlite3VdbeAddOp(v, OP_MakeRecord, nColumn, 0);

      if( aff ){

        sqlite3VdbeChangeP3(v, -1, aff, P3_STATIC);

      }

      sqlite3VdbeAddOp(v, OP_IdxInsert, iParm, 0);

      break;

    }

    /* Construct a record from the query result, but instead of

    ** saving that record, use it as a key to delete elements from

    ** the temporary table iParm.

    */

    case SRT_Except: {

      int addr;

      addr = sqlite3VdbeAddOp(v, OP_MakeRecord, nColumn, 0);

      sqlite3VdbeChangeP3(v, -1, aff, P3_STATIC);

      sqlite3VdbeAddOp(v, OP_NotFound, iParm, addr+3);

      sqlite3VdbeAddOp(v, OP_Delete, iParm, 0);

      break;

    }

#endif

    /* Store the result as data using a unique key.

    */