/*** 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.310 2006/03/26 01:21:23 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->addrOpenVirt[0] = -1;  pNew->addrOpenVirt[1] = -1;  pNew->addrOpenVirt[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*/static Expr *createIdExpr(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 = createIdExpr(zCol);  pE2a = createIdExpr(zCol);  if( zAlias1==0 ){    zAlias1 = pTab1->zName;  }  pE1b = createIdExpr(zAlias1);  if( zAlias2==0 ){    zAlias2 = pTab2->zName;  }  pE2b = createIdExpr(zAlias2);  pE1c = sqlite3Expr(TK_DOT, pE1b, pE1a, 0);  pE2c = sqlite3Expr(TK_DOT, pE2b, pE2a, 0);  pE = sqlite3Expr(TK_EQ, pE1c, pE2c, 0);  ExprSetProperty(pE, EP_FromJoin);  pE->iRightJoinTable = iRightJoinTable;  *ppExpr = sqlite3ExprAnd(*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);