/*

** 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.476 2008/09/23 09:36:10 drh Exp $

*/

#include "sqliteInt.h"

/*

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

** the select structure itself.

*/

static void clearSelect(sqlite3 *db, Select *p){

  sqlite3ExprListDelete(db, p->pEList);

  sqlite3SrcListDelete(db, p->pSrc);

  sqlite3ExprDelete(db, p->pWhere);

  sqlite3ExprListDelete(db, p->pGroupBy);

  sqlite3ExprDelete(db, p->pHaving);

  sqlite3ExprListDelete(db, p->pOrderBy);

  sqlite3SelectDelete(db, p->pPrior);

  sqlite3ExprDelete(db, p->pLimit);

  sqlite3ExprDelete(db, p->pOffset);

}

/*

** Initialize a SelectDest structure.

*/

void sqlite3SelectDestInit(SelectDest *pDest, int eDest, int iParm){

  pDest->eDest = eDest;

  pDest->iParm = iParm;

  pDest->affinity = 0;

  pDest->iMem = 0;

  pDest->nMem = 0;

}

/*

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

** structure.

*/

Select *sqlite3SelectNew(

  Parse *pParse,        /* Parsing context */

  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;

  sqlite3 *db = pParse->db;

  pNew = sqlite3DbMallocZero(db, 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(pParse, 0, sqlite3Expr(db,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->selFlags = isDistinct ? SF_Distinct : 0;

  pNew->op = TK_SELECT;

  assert( pOffset==0 || pLimit!=0 );

  pNew->pLimit = pLimit;

  pNew->pOffset = pOffset;

  pNew->addrOpenEphm[0] = -1;

  pNew->addrOpenEphm[1] = -1;

  pNew->addrOpenEphm[2] = -1;

  if( db->mallocFailed ) {

    clearSelect(db, pNew);

    if( pNew!=&standin ) sqlite3DbFree(db, pNew);

    pNew = 0;

  }

  return pNew;

}

/*

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

*/

void sqlite3SelectDelete(sqlite3 *db, Select *p){

  if( p ){

    clearSelect(db, p);

    sqlite3DbFree(db, 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 *zSp = " ";

    assert( pB!=0 );

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

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

       "%T %T%s%T", pA, pB, zSp, 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;

}

/*

** Set the token to the double-quoted and escaped version of the string pointed

** to by z. For example;

**

**    {a"bc}  ->  {"a""bc"}

*/

static void setQuotedToken(Parse *pParse, Token *p, const char *z){

  /* Check if the string appears to be quoted using "..." or `...`

  ** or [...] or '...' or if the string contains any " characters.  

  ** If it does, then record a version of the string with the special

  ** characters escaped.

  */

  const char *z2 = z;

  if( *z2!='[' && *z2!='`' && *z2!='\'' ){

    while( *z2 ){

      if( *z2=='"' ) break;

      z2++;

    }

  }

  if( *z2 ){

    /* String contains " characters - copy and quote the string. */

    p->z = (u8 *)sqlite3MPrintf(pParse->db, "\"%w\"", z);

    if( p->z ){

      p->n = strlen((char *)p->z);

      p->dyn = 1;

    }

  }else{

    /* String contains no " characters - copy the pointer. */

    p->z = (u8*)z;

    p->n = (z2 - z);

    p->dyn = 0;

  }

}

/*

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

*/

Expr *sqlite3CreateIdExpr(Parse *pParse, const char *zName){

  Token dummy;

  setToken(&dummy, zName);

  return sqlite3PExpr(pParse, 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(

  Parse *pParse,           /* Parsing context */

  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 */

  int isOuterJoin          /* True if dealing with an OUTER join */

){

  Expr *pE1a, *pE1b, *pE1c;

  Expr *pE2a, *pE2b, *pE2c;

  Expr *pE;

  pE1a = sqlite3CreateIdExpr(pParse, zCol);

  pE2a = sqlite3CreateIdExpr(pParse, zCol);

  if( zAlias1==0 ){

    zAlias1 = pTab1->zName;

  }

  pE1b = sqlite3CreateIdExpr(pParse, zAlias1);

  if( zAlias2==0 ){

    zAlias2 = pTab2->zName;

  }

  pE2b = sqlite3CreateIdExpr(pParse, zAlias2);

  pE1c = sqlite3PExpr(pParse, TK_DOT, pE1b, pE1a, 0);

  pE2c = sqlite3PExpr(pParse, TK_DOT, pE2b, pE2a, 0);

  pE = sqlite3PExpr(pParse, TK_EQ, pE1c, pE2c, 0);

  if( pE && isOuterJoin ){

    ExprSetProperty(pE, EP_FromJoin);

    pE->iRightJoinTable = iRightJoinTable;

  }

  *ppExpr = sqlite3ExprAnd(pParse->db,*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;

    int isOuter;

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

    isOuter = (pRight->jointype & JT_OUTER)!=0;

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

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

    */

    if( pRight->jointype & JT_NATURAL ){

      if( pRight->pOn || pRight->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(pParse, zName, pLeftTab, pLeft->zAlias, 

                              pRightTab, pRight->zAlias,

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

        }

      }

    }

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

    */

    if( pRight->pOn && pRight->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( pRight->pOn ){

      if( isOuter ) setJoinExpr(pRight->pOn, pRight->iCursor);

      p->pWhere = sqlite3ExprAnd(pParse->db, p->pWhere, pRight->pOn);

      pRight->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( pRight->pUsing ){

      IdList *pList = pRight->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(pParse, zName, pLeftTab, pLeft->zAlias, 

                            pRightTab, pRight->zAlias,

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

      }

    }

  }

  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 */

  int regData            /* Register holding data to be sorted */

){

  Vdbe *v = pParse->pVdbe;

  int nExpr = pOrderBy->nExpr;

  int regBase = sqlite3GetTempRange(pParse, nExpr+2);

  int regRecord = sqlite3GetTempReg(pParse);

  sqlite3ExprCodeExprList(pParse, pOrderBy, regBase, 0);

  sqlite3VdbeAddOp2(v, OP_Sequence, pOrderBy->iECursor, regBase+nExpr);

  sqlite3ExprCodeMove(pParse, regData, regBase+nExpr+1, 1);

  sqlite3VdbeAddOp3(v, OP_MakeRecord, regBase, nExpr + 2, regRecord);

  sqlite3VdbeAddOp2(v, OP_IdxInsert, pOrderBy->iECursor, regRecord);

  sqlite3ReleaseTempReg(pParse, regRecord);

  sqlite3ReleaseTempRange(pParse, regBase, nExpr+2);

  if( pSelect->iLimit ){

    int addr1, addr2;

    int iLimit;

    if( pSelect->iOffset ){

      iLimit = pSelect->iOffset+1;

    }else{

      iLimit = pSelect->iLimit;

    }

    addr1 = sqlite3VdbeAddOp1(v, OP_IfZero, iLimit);

    sqlite3VdbeAddOp2(v, OP_AddImm, iLimit, -1);

    addr2 = sqlite3VdbeAddOp0(v, OP_Goto);

    sqlite3VdbeJumpHere(v, addr1);

    sqlite3VdbeAddOp1(v, OP_Last, pOrderBy->iECursor);

    sqlite3VdbeAddOp1(v, OP_Delete, pOrderBy->iECursor);

    sqlite3VdbeJumpHere(v, addr2);

    pSelect->iLimit = 0;

  }

}

/*

** 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 */

){

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

    int addr;

    sqlite3VdbeAddOp2(v, OP_AddImm, p->iOffset, -1);

    addr = sqlite3VdbeAddOp1(v, OP_IfNeg, p->iOffset);

    sqlite3VdbeAddOp2(v, OP_Goto, 0, iContinue);

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

    sqlite3VdbeJumpHere(v, addr);

  }

}

/*

** Add code that will check to make sure the N registers starting at iMem

** form a distinct entry.  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(

  Parse *pParse,     /* Parsing and code generating context */

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

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

  int N,             /* Number of elements */

  int iMem           /* First element */

){

  Vdbe *v;

  int r1;

  v = pParse->pVdbe;

  r1 = sqlite3GetTempReg(pParse);

  sqlite3VdbeAddOp3(v, OP_MakeRecord, iMem, N, r1);

  sqlite3VdbeAddOp3(v, OP_Found, iTab, addrRepeat, r1);

  sqlite3VdbeAddOp2(v, OP_IdxInsert, iTab, r1);

  sqlite3ReleaseTempReg(pParse, r1);

}

/*

** Generate an error message when a SELECT is used within a subexpression

** (example:  "a IN (SELECT * FROM table)") but it has more than 1 result

** column.  We do this in a subroutine because the error occurs in multiple

** places.

*/

static int checkForMultiColumnSelectError(

  Parse *pParse,       /* Parse context. */

  SelectDest *pDest,   /* Destination of SELECT results */

  int nExpr            /* Number of result columns returned by SELECT */

){

  int eDest = pDest->eDest;

  if( nExpr>1 && (eDest==SRT_Mem || eDest==SRT_Set) ){

    sqlite3ErrorMsg(pParse, "only a single result allowed for "

       "a SELECT that is part of an expression");

    return 1;

  }else{

    return 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 void selectInnerLoop(

  Parse *pParse,          /* The parser context */

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

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